Solving the optimum communication spanning tree problem
| Autor: | Carlos Luna-Mota, Ivan Contreras, Elena Fernández, Carlos Armando Zetina |
|---|---|
| Přispěvatelé: | 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ó |
| Rok vydání: | 2019 |
| Předmět: |
Anàlisi numèrica
050210 logistics & transportation Mathematical optimization 021103 operations research Information Systems and Management Spanning tree General Computer Science Spanning trees Computer science Benders decomposition 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Matemàtiques i estadística::Anàlisi numèrica [Àrees temàtiques de la UPC] Orders of magnitude (bit rate) Set (abstract data type) Modeling and Simulation 0502 economics and business Networks Heuristics Network optimization 65 Numerical analysis::65K Mathematical programming optimization and variational techniques [Classificació AMS] Numerical analysis |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| ISSN: | 0377-2217 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect