Skip to Main content Skip to Navigation
Journal articles

Lagrangian and branch-and-cut approaches for upgrading spanning tree problems

Eduardo Álvarez-Miranda 1 Markus Sinnl 2, 3
2 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Problems aiming at finding budget constrained optimal upgrading schemes to improve network performance have received attention over the last two decades. In their general setting, these problems consist of designing a network and, simultaneously, allocating (limited) upgrading resources in order to enhance the performance of the designed network. In this paper we address two particular optimal upgrading network design problems; in both cases, the sought-after layout corresponds to a spanning tree of the input network and upgrading decisions are to be taken on nodes. We design Mixed Integer Programming-based algorithmic schemes to solve the considered problems: Lagrangian relaxation approaches and branch-and-cut algorithms. Along with the designed algorithms, different enhancements, including valid inequalities, primal heuristic and variable fixing procedures, are proposed. Using two set of instances, we experimentally compare the designed algorithms and explore the benefits of the devised enhancements. The results show that the proposed approaches are effective for solving to optimality most of the instances in the testbed, or manage to obtain solutions and bounds giving very small optimality gaps. Besides, the proposed enhancements turn out to be beneficial for improving the performance of the algorithms.
Document type :
Journal articles
Complete list of metadata
Contributor : Markus Sinnl Connect in order to contact the contributor
Submitted on : Monday, December 18, 2017 - 11:05:24 AM
Last modification on : Tuesday, August 24, 2021 - 4:52:08 PM




Eduardo Álvarez-Miranda, Markus Sinnl. Lagrangian and branch-and-cut approaches for upgrading spanning tree problems. Computers and Operations Research, Elsevier, 2017, 83, pp.13-27. ⟨10.1016/j.cor.2017.01.014⟩. ⟨hal-01666285⟩



Record views