Abstract
We study the post-timetabling \emph{lecture-hall assignment problem}, in which a fixed weekly timetable and realized student enrollments are given, and the decision is to assign each lecture to a compatible hall so as to minimize the walking burden imposed on students moving between consecutive lectures and a penalty for feasible but non-ideal compatibility of halls-lecture. The problem combines a quadratic assignment objective, driven by the product of shared enrollments and hall-to-hall distances, with interval-scheduling feasibility constraints and hall-capacity restrictions. We prove that the problem is NP-hard and that every approximation lower bound for the classical quadratic assignment problem carries over, already in a single-day, two-block special case. We develop three exact formulations: a bilinear mixed-integer quadratic program, a compact mixed-integer linear program with one auxiliary distance variable per successor pair, and a constraint-programming model. All of these formulations admitting a natural daily decomposition. To tighten the relaxations we introduce biclique distance cuts that dominate the standard pairwise linking inequalities, together with Chv\'atal-Gomory capacity-dominance cuts and a safe compatibility-preprocessing procedure. The framework also accommodates common timetabling side constraints such as hard and soft \emph{SameRoom} and \emph{SameAttendees} requirements, for which biclique-strengthened linearizations are derived. A comprehensive numerical experiment covers daily instances derived from five large ITC~2019 competition benchmarks and from a 2023 institutional dataset from Lancaster University. The compact linearized program emerges as the most robust formulation, and biclique strengthening is the dominant modeling device: it closes virtually all of the root-relaxation gap and lifts the number of proven-optimal solves substantially, while cutting median solver runtimes by roughly an order of magnitude. The results demonstrate that realistically sized lecture-hall assignment instances can be solved to optimality or near-optimality within minutes, and frequently even within seconds, by off-the-shelf mixed-integer programming solver once the biclique structure of the quadratic walking term is exploited.

This publication has 27 references indexed in Scilit: