| dc.contributor.author | Furini, Fabio | |
| dc.contributor.author | Malaguti, Enrico | |
| dc.contributor.author | Santini, Alberto | |
| dc.date.accessioned | 2019-04-12T14:19:26Z | |
| dc.date.available | 2019-04-12T14:19:26Z | |
| dc.date.issued | 2018 | |
| dc.identifier.issn | 03050548 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/18641 | |
| dc.language.iso | en | en |
| dc.subject | Vertex Coloring | en |
| dc.subject | Partitioning coloring | en |
| dc.subject | Selective coloring | en |
| dc.subject | Column generation | en |
| dc.subject | Branch-and-Price algorithm | en |
| dc.subject.ddc | 005 | en |
| dc.title | An exact algorithm for the Partition Coloring Problem | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | 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. | en |
| dc.relation.isversionofjnlname | Computers & Operations Research | |
| dc.relation.isversionofjnlvol | 92 | en |
| dc.relation.isversionofjnldate | 2018-04 | |
| dc.relation.isversionofjnlpages | 170-181 | en |
| dc.relation.isversionofdoi | 10.1016/j.cor.2017.12.019 | en |
| dc.subject.ddclabel | Programmation, logiciels, organisation des données | en |
| dc.relation.forthcoming | non | en |
| dc.relation.forthcomingprint | non | en |
| dc.description.ssrncandidate | non | en |
| dc.description.halcandidate | oui | en |
| dc.description.readership | recherche | en |
| dc.description.audience | International | en |
| dc.relation.Isversionofjnlpeerreviewed | non | en |
| dc.relation.Isversionofjnlpeerreviewed | non | en |
| dc.date.updated | 2019-03-27T14:50:54Z | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 461036 | |
| hal.person.labIds | 526081 | |
| hal.identifier | hal-02098417 | * |
