The Optimum Communication Spanning Tree Problemproperties, models and algorithms
- Luna Mota, Carlos
- Elena Fernández Aréizaga Directora
Universidad de defensa: Universitat Politècnica de Catalunya (UPC)
Fecha de defensa: 01 de febrero de 2016
- Justo Puerto Albandoz Presidente/a
- María Albareda Sambola Secretario/a
- Gerhard Reinelt Vocal
Tipo: Tesis
Resumen
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.