|
Title:
|
Solving the optimum communication spanning tree problem
|
|
Author:
|
Zetina, Carlos Armando; Contreras Aguilar, Iván; Fernández Aréizaga, Elena; Luna Mota, Carlos
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa; Universitat Politècnica de Catalunya. GNOM - Grup d'Optimització Numèrica i Modelització |
|
Abstract:
|
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able to prove optimality for five unsolved instances in the literature and four from a new set of larger instances. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica
-Numerical analysis
-Networks
-Network optimization
-Benders decomposition
-Spanning trees
-Anàlisi numèrica
-Classificació AMS::65 Numerical analysis::65K Mathematical programming, optimization and variational techniques |
|
Rights:
|
|
|
Document type:
|
Article - Submitted version
Article |
|
Published by:
|
Elsevier
|
|
Share:
|
|
