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
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - 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 metadatas

https://hal.inria.fr/hal-01666285
Contributor : Markus Sinnl <>
Submitted on : Monday, December 18, 2017 - 11:05:24 AM
Last modification on : Tuesday, June 18, 2019 - 3:10:22 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

195