Graph Coloring Facets from All-Different SystemsLecture Notes in Computer Science
Date of Original Version5-1-2012
Abstract or DescriptionWe explore the idea of obtaining valid inequalities for a 0-1 model from a 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-diff 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 cyclic structures and show that they are stronger than known cuts. For example, when an existing separation algorithm identifies odd hole cuts, we can supply stronger cuts with no additional calculation. In addition, we generalize odd hole cuts to odd cycle cuts that are stronger than any collection of odd hole cuts.
Citation InformationDavid Bergman and John N. Hooker. "Graph Coloring Facets from All-Different Systems" Lecture Notes in Computer Science Vol. 7298 (2012) p. 50 - 65
Available at: http://works.bepress.com/jnhooker/63/