Exact approaches for solving a covering problem with capacitated subtrees - Archive ouverte HAL Access content directly
Journal Articles Computers and Operations Research Year : 2019

Exact approaches for solving a covering problem with capacitated subtrees

(1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
CovProbWCapSubtrees_Rev2.pdf (824.78 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02053563 , version 1 (01-03-2019)

Identifiers

Cite

François Clautiaux, Jeremy Guillot, Pierre Pesneau. Exact approaches for solving a covering problem with capacitated subtrees. Computers and Operations Research, 2019, 105, pp.85-101. ⟨10.1016/j.cor.2019.01.008⟩. ⟨hal-02053563⟩
118 View
338 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More