The lecture-hall quadratic assignment problem
Author:
Preprint
- 30 April 2026
- preprint
- Published by Elsevier in SSRN Electronic Journal
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.Keywords
This publication has 27 references indexed in Scilit:
- Modelling and solving the university course timetabling problem with hybrid teaching considerationsJournal of Scheduling, 2024
- Real-world university course timetabling at the International Timetabling Competition 2019Journal of Scheduling, 2024
- A mixed-integer programming approach for solving university course timetabling problemsJournal of Scheduling, 2022
- New exact approaches to row layout problemsMathematical Programming Computation, 2019
- Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and resultsAnnals of Operations Research, 2010
- Interval scheduling: A surveyNaval Research Logistics (NRL), 2007
- Recent advances in the solution of quadratic assignment problemsMathematical Programming, 2003
- Solving large quadratic assignment problems on computational gridsMathematical Programming, 2002
- On the quadratic assignment problemDiscrete Applied Mathematics, 1983
- An algorithm for the quadratic assignment problem using Bender's decompositionEuropean Journal of Operational Research, 1978