An exact algorithm for the Partition Coloring Problem. (April 2018) - Furini, Fabio; Malaguti, Enrico; Santini, Alberto
Highlights: A generalization of the Vertex Coloring Problem where the vertex set is partitioned. A vertex for each subset of the partition has to be colored. A new Integer Linear Programming formulation with an exponential number of variables. A Branch-and-Price algorithm initialized via a metaheuristic algorithm. Computational experiments. Abstract: 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 neighborhood 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 favorably with the current state-of-the-art exact algorithm.