A branch-price-and-cut algorithm for graph coloring

Branch-and-price approaches for graph coloring using the set covering formulation have been shown to be effective, particularly in computing strong lower bounds. This thesis proposes the addition of both maximally-violated mod-k cutting planes and odd-cycle cutting planes to ex- tend the existing branch-and-price algorithms. Algorithms to efficiently separate these classes of cutting planes are proposed. A combinatorial algorithm for the modified pricing algorithm is proposed, and the resulting branch-price-and-cut algorithm is tested on the DIMACS instances. The branch-price-and-cut algorithm has similar performance as the branch-and-price algorithm when applying cuts at the root node. Maximally violated mod-k cutting planes are shown to be effective in increasing the lower bound of the root node for insertion graphs, and odd-cycle cuts are shown to be effective in increasing the lower bound of dense DIMACS instances. Various branching strategies from the literature are also surveyed, and a new branching strat- egy is proposed which outperforms the existing branching strategies. Using this new branching strategy, we are able to solve all tested graphs with less than 100 vertices, solving the myciel6 instance, all FullIns and 3 insertion graphs using a branch-and-price algorithm for the first time. The open instance 5-FullIns 4 is solved by the new branch-and-price algorithm.