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.
Type de document :
Article dans une revue
Computers & Operations Research, 2017, 83, pp.13-27. 〈10.1016/j.cor.2017.01.014〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01666285
Contributeur : Markus Sinnl <>
Soumis le : lundi 18 décembre 2017 - 11:05:24
Dernière modification le : mardi 3 juillet 2018 - 11:34:58

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

155