Back to Search Start Over

Graph coloring inequalities from all-different systems.

Graph coloring inequalities from all-different systems.

Authors :
Bergman, David
Hooker, J.
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