A branch-and-price approach for the partition coloring problem

This work proposes a new integer programming model for the partition coloring problem and a branch-and-price algorithm to solve it. Experiments are reported for random graphs and instances originating from routing and wavelength assignment problems arising in telecommunication network design. We show that our method largely outperforms previously existing approaches.