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.

A COMPUTATIONAL STUDY OF A CUTTING PLANE ALGORITHM FOR UNIVERSITY COURSE TIMETABLING

Avella P;
2005

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.
File in questo prodotto:
File Dimensione Formato  
Avella, Vasiliev - Cutting planes for University Course Timetabling.pdf

non disponibili

Licenza: Non specificato
Dimensione 787.38 kB
Formato Adobe PDF
787.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12070/3001
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 39
  • ???jsp.display-item.citation.isi??? 33
social impact