Exact approaches for solving a covering problem with capacitated subtrees

François Clautiaux 1 Jeremy Guillot 1 Pierre Pesneau 1
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02053563
Contributor : Pierre Pesneau <>
Submitted on : Friday, March 1, 2019 - 2:11:19 PM
Last modification on : Thursday, May 16, 2019 - 3:54:07 PM
Long-term archiving on : Thursday, May 30, 2019 - 3:05:50 PM

File

CovProbWCapSubtrees_Rev2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02053563, version 1

Citation

François Clautiaux, Jeremy Guillot, Pierre Pesneau. Exact approaches for solving a covering problem with capacitated subtrees. Computers and Operations Research, Elsevier, 2019, 105, pp.85-101. ⟨hal-02053563⟩

Share

Metrics

Record views

76

Files downloads

83