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

Author

Luna Mota, Carlos

Director

Fernández, Elena (Fernández Aréizaga)

Date of defense

2016-02-01

Pages

113 p.



Department/Institute

Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa

Abstract

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.

Keywords

Network design; Spanning trees; Combinatorial optimization

Subjects

519.1 - Combinatorial analysis. Graph theory

Knowledge Area

Àrees temàtiques de la UPC::Matemàtiques i estadística

Documents

TCLM1de1.pdf

1.002Mb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/3.0/es/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/3.0/es/

This item appears in the following Collection(s)