Graph Coloring with Decision Diagrams
W.-J. van Hoeve (vanhoeveandrew.cmu.edu)
Abstract: We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts are removed by refining the decision diagram. We prove that in the best case, our approach may use exponentially smaller diagrams than exact diagrams for proving optimality. We also develop a primal heuristic based on the decision diagram to find a feasible solution at each iteration. We provide an experimental evaluation on all 137 DIMACS graph coloring instances. Our procedure can solve 52 instances optimally, of which 44 are solved within 1 minute. We also report an improved lower bound for instance C2000.9.
Keywords: Graph coloring, Decision diagrams, Integer programming
Category 1: Combinatorial Optimization
Category 2: Integer Programming
Citation: Under review.
Entry Submitted: 01/16/2021
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|