Optimization Online


An Exact Algorithm for the Partition Coloring Problem

Fabio Furini (fabio.furini***at***dauphine.fr)
Enrico Malaguti (enrico.malaguti***at***unibo.it)
Alberto Santini (a.santini***at***unibo.it)

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

Download: [PDF]

Entry Submitted: 12/20/2016
Entry Accepted: 12/20/2016
Entry Last Modified: 07/06/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society