• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
5777.pdf (345.4Kb)
Type
Article accepté pour publication ou publié
Date
2018
Journal name
Computers & Operations Research
Volume
92
Pages
170-181
Publication identifier
10.1016/j.cor.2017.12.019
Metadata
Show full item record
Author(s)
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
D.E.I. - University of Bologna.
Santini, Alberto
D.E.I. - University of Bologna.
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 algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
  • Thumbnail
    A note on selective line-graphs and partition colorings 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
  • Thumbnail
    Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation 
    Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
  • Thumbnail
    Mathematical formulations for the Balanced Vertex k-Separator Problem 
    Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
  • Thumbnail
    On integer and bilevel formulations for the k-vertex cut problem 
    Furini, Fabio; Ljubić, Ivana; Malaguti, Enrico; Paronuzzi, Paolo (2020) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo