Título:
A new effective mathematical programming model to design CDN topology
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Bentos, Milton
Tutor:
Robledo, Franco
Risso, Claudio
Risso, Claudio
Tipo de documento:
Tesis de maestría
Editor:
Palabras clave:
Flow-based model
Flexible model
Effective optimization
Linealization
Mixed-integer problem formulation
Ford-Fulkerson algorithm
Steiner Tree Problem
Quality of Service Multicast Tree Problem
Flexible model
Effective optimization
Linealization
Mixed-integer problem formulation
Ford-Fulkerson algorithm
Steiner Tree Problem
Quality of Service Multicast Tree Problem
Descriptores:
Año de publicación:
2019
Contenido:
Resumen:
The Steiner Tree Problem is an umbrella of combinatorial optimization problems in
graphs, most of them NP-Hard, within which, the Steiner Tree Problem in graphs (STP) is
perhaps one of the most famous and widely studied. The STP consists in optimally interconnect
a given set of terminal or mandatory nodes within a graph with edges of positive weights,
eventually using other optional nodes. It has a wide range of applications from circuit layouts
to network design, so plenty of models to find its exact solutions have been crafted. Traditionally,
due to its intrinsic complexity, heuristic approaches have been used to find good quality
solutions to the STP. Currently, the outstanding computing power resulting from combining
developments in hardware and software capabilities makes it possible to rely upon exact
formulations and generic algorithms to solve complex instances of the problem. This work
introduces a flow-based mixed-integer problem formulation (MIP) for the STP using the
SteinLib, a reference test-set repository. Later on, that MIP formulation is modified to solve
the Quality of Service Multicast Tree problem (QoSTP). To the best of our knowledge, there
is no previous MIP formulation. While existing approaches go all the way of approximation
algorithms to find solutions, this MIP formulation shows promising experimental results.
Optimal solutions are found for several instances, while low feasible-to-optimal gaps were
obtained for most of the remaining ones.
Descripción:
Editorial:
Udelar.FI.
EN:
Financiadores:
Citación:
Bentos, M. A new effective mathematical programming model to design CDN topology [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO, 2019.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
https://hdl.handle.net/20.500.12008/26247
ISBN:
e-ISBN:
ISSN:
1688-2792
ISMN:
Otros identificadores:
Título Obtenido:
Magíster en Investigación de Operaciones
Facultad o Servicio que otorga el Título:
Universidad de la República (Uruguay). Facultad de Ingeniería
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| BEN19.pdf | Tesis de maestría | 848.76 KB | Adobe PDF |