
An exact algorithm for the Partition Coloring Problem
Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018), An exact algorithm for the Partition Coloring Problem, Computers & Operations Research, 92, p. 170-181. 10.1016/j.cor.2017.12.019
View/ Open
Type
Article accepté pour publication ou publiéDate
2018Journal name
Computers & Operations ResearchVolume
92Pages
170-181
Publication identifier
Metadata
Show full item recordAuthor(s)
Furini, FabioLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
Santini, Alberto
Abstract (EN)
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.Subjects / Keywords
Vertex Coloring; Partitioning coloring; Selective coloring; Column generation; Branch-and-Price algorithmRelated items
Showing items related by title and author.
-
Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
-
Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
-
Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié