This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation.
After computing upper and lower bounds at the root node using heuristic and column generation techniques, BPCOL+ reduces the size of the ZDD through maximal stable set reduction techniques that exploit alternative dual vectors.
Computational experiments on the 137 DIMACS benchmark instances and on 5,000 recently proposed Erd\H{o}s–R\’enyi instances show that BPCOL+ outperforms existing exact branch-and-price algorithms and remains highly competitive with state-of-the-art SAT-based exact solvers. In particular, BPCOL+ solves 96 DIMACS instances within one hour and proves optimality for 4,641 of the 5,000 Erd\H{o}s–R\’enyi instances.
Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results
\(\)