An Exact Algorithm for the Partition Coloring Problem
Fabio Furini (fabio.furinidauphine.fr)
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 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.
Keywords: VertexColoring,PartitioningColoring,SelectiveColoring, Column Generation, Branch-and-Price.
Category 1: Combinatorial Optimization
Category 2: Combinatorial Optimization (Graphs and Matroids )
Citation: F. Furini, E. Malaguti, S. Santini. An Exact Algorithm for the Partition Coloring Problem. Optimization Online, 2016
Entry Submitted: 12/20/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|