Finite-Domain Cuts for Graph Coloring.pdf.pdf' (236.63 kB)

Finite-Domain Cuts for Graph Coloring

Download (236.63 kB)
journal contribution
posted on 01.11.2005, 00:00 by David Bergman, John N. Hooker

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.

History

Publisher Statement

All Rights Reserved

Date

01/11/2005

Exports

Exports