GALAS: Greedy Local-Adjusting Room Allocation Framework

In this paper, we study the room allocation problem to optimize room utilization in allocating rooms for courses under all the conflicting constraints, which has been proven NP-complete. We first formulate the problem as an Integer Linear Program (ILP) so it can be solved optimally using an ILP solver. However, solving ILP incurs an exponential run-time complexity, which is impractical for real-world applications. To address this issue, we propose Greedy Algorithm plus Local Adjustment via Swaps (GALAS), a greedy heuristic framework with a reduced run-time that finds near-optimal room allocation solutions. GALAS uses multiple greedy strategies to quickly generate feasible schedules and then optimize them via a sequence of local swap operations. We evaluate the performance of the GALAS on synthetic and real-world datasets. The experimental results show that the GALAS outperforms the state-of-the-art in room utilization and run-time simultaneously. On average, GALAS achieves a near-optimal performance of 98.5% to the optimal solution.