A wide branching strategy for the graph coloring problem

David R. Morrison, Jason J. Sauppe, Edward C. Sewell, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

Branch-and-price algorithms for the graph coloring problem use an exponentially sized independent set-based integer programming formulation to produce usually tight lower bounds to enable more aggressive pruning in the branch-and-bound tree. One major problem inherent to any branch-and-price scheme for graph coloring is that to avoid destroying the pricing problem structure during column generation, difficult-to-implement branching rules that modify the underlying graph must be used. This paper proposes an alternative branching strategy that does not change the graph to solve the pricing problem but rather modifies the search tree to require fewer calls to difficult instances of the pricing problem. This approach, called wide branching, generates many subproblems at each node in the branch-and-price tree; this significantly reduces the length of any path through the search tree. In contrast, traditional deep branching only creates two subproblems per node, assigning a variable to either 0 or 1. A delayed branching procedure is introduced that prevents the branching factor at any particular node from growing too large in this scheme. Finally, computational results are presented that show the wide branching strategy to be competitive with state-of-the-art graph coloring solvers.

Original languageEnglish (US)
Pages (from-to)704-717
Number of pages14
JournalINFORMS Journal on Computing
Volume26
Issue number4
DOIs
StatePublished - Sep 1 2014

Keywords

  • Branch-and-price
  • Computational experiments
  • Graph coloring
  • Integer programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A wide branching strategy for the graph coloring problem'. Together they form a unique fingerprint.

Cite this