On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling
Authors:
Preprint
Abstract
Vertex colouring is a well-known problem in combinatorial optimisation, whose alternative integer programming formulations have recently attracted considerable attention. This paper briefly surveys seven known formulations of vertex colouring and introduces a formulation of vertex colouring using a suitable clique partition of the graph. This formulation is applicable in timetabling applications, where such a clique partition of the conflict graph is given implicitly. In contrast with some alternatives, the presented formulation can also be easily extended to accommodate complex performance indicators (``soft constraints'') imposed in a number of real-life course timetabling applications. Its performance depends on the quality of the clique partition, but encouraging empirical results for the Udine Course Timetabling problem are reported.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Constraint Integer Programming: A New Approach to Integrate CP and MIP2008
- Models and solution techniques for frequency assignment problemsAnnals of Operations Research, 2007
- Packing and partitioning orbitopesMathematical Programming, 2007
- Application of a real-world university-course timetabling model solved by integer programmingOR Spectrum, 2006
- Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a Few Seconds2006
- A Computational Study of a Cutting Plane Algorithm for University Course TimetablingJournal of Scheduling, 2005
- Exploiting orbits in symmetric ILPMathematical Programming, 2003
- Pruning by isomorphism in branch-and-cutMathematical Programming, 2002
- Graph Colouring and the Probabilistic Method2002
- Zero Knowledge and the Chromatic NumberJournal of Computer and System Sciences, 1998