|
Título:
|
Solving the optimum communication spanning tree problem
|
|
Autor/a:
|
Zetina, Carlos Armando; Contreras Aguilar, Iván; Fernández Aréizaga, Elena; Luna Mota, Carlos
|
|
Otros autores:
|
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 |
|
Materia(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 |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Artículo |
|
Editor:
|
Elsevier
|
|
Compartir:
|
|
