Skip to Main content Skip to Navigation
Journal articles

Benders decomposition for Network Design Covering Problems

Víctor Bucarey 1 Bernard Fortz 2, 3 Natividad González-Blanco 4 Martine Labbé 3 Juan Mesa 4
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université libre de Bruxelles, Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : We consider two covering variants of the network design problem. We are given a set of origin/destination (O/D) pairs and each such O/D pair is covered if there exists a path in the network from the origin to the destination whose length is not larger than a given threshold. In the first problem, called the maximal covering network design problem, one must determine a network that maximizes the total demand of the covered O/D pairs subject to a budget constraint on the design costs of the network. In the second problem, called the partial covering network design problem, the design cost is minimized while a lower bound is set on the total demand covered. After presenting formulations, we develop a Benders decomposition approach to solve the problems. Further, we consider two different stabilization methods to determine the Benders cuts as well as the addition of cut-set inequalities to the master problem. Computational experiments show the efficiency of these different aspects.
Document type :
Journal articles
Complete list of metadata
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Wednesday, February 10, 2021 - 6:06:49 PM
Last modification on : Friday, January 21, 2022 - 3:10:21 AM
Long-term archiving on: : Tuesday, May 11, 2021 - 9:06:26 PM


Files produced by the author(s)


  • HAL Id : hal-03137944, version 1



Víctor Bucarey, Bernard Fortz, Natividad González-Blanco, Martine Labbé, Juan Mesa. Benders decomposition for Network Design Covering Problems. Computers and Operations Research, Elsevier, 2022. ⟨hal-03137944⟩



Les métriques sont temporairement indisponibles