Show simple item record

An exact algorithm for the Partition Coloring Problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorFurini, Fabio
hal.structure.identifierD.E.I. - University of Bologna.
dc.contributor.authorMalaguti, Enrico
hal.structure.identifier
dc.contributor.authorSantini, Alberto
dc.date.accessioned2019-04-12T14:19:26Z
dc.date.available2019-04-12T14:19:26Z
dc.date.issued2018
dc.identifier.issn03050548
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18641
dc.language.isoenen
dc.subjectVertex Coloringen
dc.subjectPartitioning coloringen
dc.subjectSelective coloringen
dc.subjectColumn generationen
dc.subjectBranch-and-Price algorithmen
dc.subject.ddc005en
dc.titleAn exact algorithm for the Partition Coloring Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameComputers & Operations Research
dc.relation.isversionofjnlvol92en
dc.relation.isversionofjnldate2018-04
dc.relation.isversionofjnlpages170-181en
dc.relation.isversionofdoi10.1016/j.cor.2017.12.019en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-27T14:50:54Z
hal.identifierhal-02098417*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
partitioncoloring_furinimalagu ...
Size:
371.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record