An exact algorithm for the Partition Coloring Problem. (April 2018)

• Record Type: Journal Article
• Authors: Furini, Fabio; Malaguti, Enrico; Santini, Alberto
• Is Part Of: Computers & operations research. Volume 92(2018)
• Page Start: 170
• Page End: 181
• Publication Date: 2018-04
• Subjects: Vertex Coloring -- Partitioning coloring -- Selective coloring -- Column generation -- Branch-and-Price algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.12.019
• Languages: English
• ISSNs: 0305-0548

Abstract

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.