Exact approaches for solving a covering problem with capacitated subtrees
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | CLAUTIAUX, François | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | GUILLOT, Jeremy | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | PESNEAU, Pierre | |
dc.date.accessioned | 2024-04-04T03:01:49Z | |
dc.date.available | 2024-04-04T03:01:49Z | |
dc.date.issued | 2019-05 | |
dc.identifier.issn | 0305-0548 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/192927 | |
dc.description.abstractEn | In this document, we present a covering problem where vertices of a graph have to be covered by rooted subtrees. We present three mixed-integer linear programming models, two of which are compact while the other is based on Dantzig-Wolfe decomposition. In the latter case, we focus on the column generation subproblem, for which we propose several algorithms. Numerical results are obtained using instances from the literature and instances based on a real-life districting application. Experiments show that the branch-and-price algorithm is able to solve much bigger instances than the compact model, which is limited to very small instance sizes. | |
dc.language.iso | en | |
dc.publisher | Elsevier | |
dc.subject.en | Dantzig-Wolfe decomposition | |
dc.subject.en | Column generation | |
dc.subject.en | Covering problems | |
dc.subject.en | Dynamic programming | |
dc.subject.en | Branch-and-bound | |
dc.title.en | Exact approaches for solving a covering problem with capacitated subtrees | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1016/j.cor.2019.01.008 | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
bordeaux.journal | Computers and Operations Research | |
bordeaux.page | 85-101 | |
bordeaux.volume | 105 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-02053563 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-02053563v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Computers%20and%20Operations%20Research&rft.date=2019-05&rft.volume=105&rft.spage=85-101&rft.epage=85-101&rft.eissn=0305-0548&rft.issn=0305-0548&rft.au=CLAUTIAUX,%20Fran%C3%A7ois&GUILLOT,%20Jeremy&PESNEAU,%20Pierre&rft.genre=article |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |