An Exact Algorithm for the Partition Coloring Problem

We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation with an exponential number of variables. To solve this formulation to optimality, we design an effective Branch-and-Price algorithm. Good quality initial solutions are computed via a new metaheuristic algorithm based on adaptive large neighbourhood search. Extensive computational experiments on a benchmark test of instances from the literature show that our Branch-and-Price algorithm, combined with the new metaheuristic algorithm, is able to solve for the first time to proven optimality several open instances, and compares favourably with the current state-of-the-art exact algorithm.

Citation

F. Furini, E. Malaguti, S. Santini. An Exact Algorithm for the Partition Coloring Problem. Optimization Online, 2016

Article

Download

View An Exact Algorithm for the Partition Coloring Problem