The Optimum Communication Spanning Tree Problem: properties, models and algorithms

Autores: Carlos Luna Mota
Directores de la Tesis: Elena Fernández Aréizaga (dir. tes.)
Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2016
Idioma: inglés
Tribunal Calificador de la Tesis: Justo Puerto Albandoz (presid.) , María Albareda Sambola (secret.) , Gerhard Reinelt (voc.)
Enlaces
- Tesis en acceso abierto en: TDX
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.