The Optimum Communication Spanning Tree Problemproperties, models and algorithms
- Luna Mota, Carlos
- Elena Fernández Aréizaga Doktormutter
Universität der Verteidigung: Universitat Politècnica de Catalunya (UPC)
Fecha de defensa: 01 von Februar von 2016
- Justo Puerto Albandoz Präsident/in
- María Albareda Sambola Sekretär/in
- Gerhard Reinelt Vocal
Art: Dissertation
Zusammenfassung
For a given cost matrix and a given communication requirement matrix, the OCSTP is defined as finding a spanning tree that minimizes the operational cost of the network. OCST can be used to design of more efficient communication and transportation networks, but appear also, as a subproblem, in hub location and sequence alignment problems. This thesis studies several mixed integer linear optimization formulations of the OCSTP and proposes a new one. Then, an efficient Branch & Cut algorithm derived from the Benders decomposition of one of such formulations is used to successfully solve medium-sized instances of the OCSTP. Additionally, two new combinatorial lower bounds, two new heuristic algorithms and a new family of spanning tree neighborhoods based on the Dandelion Code are presented and tested.