Back to Search
Start Over
Graph coloring inequalities from all-different systems.
Graph coloring inequalities from all-different systems.
- Source :
- Constraints: An International Journal; Oct2014, Vol. 19 Issue 4, p404-433, 30p
- Publication Year :
- 2014
-
Abstract
- We explore the idea of obtaining valid inequalities for a 0-1 model from a finite-domain constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of all-different systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem. We focus on cuts corresponding to cycles and webs and show that they are stronger than known cuts for these structures. We also identify path cuts and show they do not strengthen the bound. Computational experiments for a set of benchmark instances reveal that finite-domain cycle cuts often deliver tighter bounds, in less time, than classical 0-1 cuts. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13837133
- Volume :
- 19
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Constraints: An International Journal
- Publication Type :
- Academic Journal
- Accession number :
- 97432428
- Full Text :
- https://doi.org/10.1007/s10601-014-9164-8