Optimization Online


Graph Coloring with Decision Diagrams

W.-J. van Hoeve (vanhoeve***at***andrew.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.

Download: [PDF]

Entry Submitted: 01/16/2021
Entry Accepted: 01/17/2021
Entry Last Modified: 01/19/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society