• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
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

Voir/Ouvrir
partitioncoloring_furinimalagutisantini_rev2.pdf (371.5Kb)
Type
Article accepté pour publication ou publié
Date
2018
Nom de la revue
Computers & Operations Research
Volume
92
Pages
170-181
Identifiant publication
10.1016/j.cor.2017.12.019
Métadonnées
Afficher la notice complète
Auteur(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
Résumé (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.
Mots-clés
Vertex Coloring; Partitioning coloring; Selective coloring; Column generation; Branch-and-Price algorithm

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    A note on selective line-graphs and partition colorings 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    Solving vertex coloring problems as maximum weight stable set problems 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo