Mostrar el registro sencillo del ítem

Exact approaches for solving a covering problem with capacitated subtrees

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorGUILLOT, Jeremy
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorPESNEAU, Pierre
dc.date.accessioned2024-04-04T03:01:49Z
dc.date.available2024-04-04T03:01:49Z
dc.date.issued2019-05
dc.identifier.issn0305-0548
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/192927
dc.description.abstractEnIn 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.isoen
dc.publisherElsevier
dc.subject.enDantzig-Wolfe decomposition
dc.subject.enColumn generation
dc.subject.enCovering problems
dc.subject.enDynamic programming
dc.subject.enBranch-and-bound
dc.title.enExact approaches for solving a covering problem with capacitated subtrees
dc.typeArticle de revue
dc.identifier.doi10.1016/j.cor.2019.01.008
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
bordeaux.journalComputers and Operations Research
bordeaux.page85-101
bordeaux.volume105
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02053563
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02053563v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem