Computer Science – Discrete Mathematics
Scientific paper
2007-10-18
Computer Science
Discrete Mathematics
Scientific paper
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.
Burke Edmund K.
Marecek Jakub
Parkes Andrew J.
Rudova Hana
No associations
LandOfFree
On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Clique-Based Integer Programming Formulation of Vertex Colouring with Applications in Course Timetabling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-708248