Finite-Domain Cuts for Graph Coloring

We explore the idea of obtaining valid inequalities from a finite-domain formulation of a problem, rather than a 0-1 formulation. A finite-domain model represents discrete choices with variables that have several possible values, as is frequently done in constraint programming. We apply the idea to graph coloring and identify facet-defining cuts that, when converted to cuts in a 0-1 model of the problem, provide tighter bounds on the chromatic number than known 0-1 cuts. In particular, we show that finite-domain cuts for webs and odd holes are superior to standard cuts, and that two cuts for an odd cycle (a generalization of an odd hole) yield substantially tighter bounds, in much less time, than hundreds or thousands of standard cuts. We also identify a large family of facet-defining cuts for intersecting systems, for which there are apparently no previously known 0-1 cuts.