| Autor: |
Burke, Edmund K., Marecek, Jakub, Parkes, Andrew J., Rudova, Hana |
| Rok vydání: |
2007 |
| Předmět: |
|
| Zdroj: |
Annals of Operations Research (2010) 179(1), 105-130 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/s10479-010-0716-z |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
