A Computational Study of a Cutting Plane Algorithm for University Course Timetabling |
| |
Authors: | Pasquale Avella Igor Vasil'Ev |
| |
Affiliation: | (1) RCOST - Research Center on Software Technology, Università del Sannio, C.so Garibaldi 107, 82100 Benevento, Italy;(2) Centro di Ricerca in Matematica Pura e Applicata, Università di Salerno, Via Ponte Don Melillo, 84084 Fisciano, (SA), Italy;(3) Institute of System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences, Lermontov Srt., 134, 664033 Irkutsk, Russia |
| |
Abstract: | In this paper, we describe a case-study where a Branch-and-Cut algorithm yields the “optimal” solution of a real-world timetabling
problem of University courses (University Course Timetabling problem).
The problem is formulated as a Set Packing problem with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing polytope,
namely Clique and Lifted Odd-Hole inequalities. We also analyze the combinatorial properties of the problem to introduce new
families of cutting planes that are not valid for the Set Packing polytope, and their separation algorithms. These cutting
planes turned out to be very effective to yield the optimal solution of a set of real-world instances with up to 69 courses,
59 teachers, and 15 rooms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|