| Metadato | Etiqueta | Valor | Idioma |
|---|---|---|---|
| dc.contributor.advisor | Tutor | Robledo, Franco | - |
| dc.contributor.advisor | Tutor | Risso, Claudio | - |
| dc.contributor.author | Autor | Bentos, Milton | - |
| dc.contributor.filiacion | Filiación | Bentos Milton, Universidad de la República (Uruguay). Facultad de Ingeniería. | - |
| dc.date.accessioned | Fecha ingreso | 2020-12-29T16:23:43Z | - |
| dc.date.available | Fecha disponible | 2020-12-29T16:23:43Z | - |
| dc.date.issued | Año de publicación | 2019 | - |
| dc.description.abstract | 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. | es |
| dc.format.extent | Extensión | 47 p. | es |
| dc.format.mimetype | Formato | application/pdf | es |
| dc.identifier.citation | 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. | es |
| dc.identifier.issn | ISSN | 1688-2792 | - |
| dc.identifier.uri | URI | https://hdl.handle.net/20.500.12008/26247 | - |
| dc.language.iso | Idioma | en | es |
| dc.publisher | Editorial | Udelar.FI. | es |
| dc.rights | Derechos | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | es |
| dc.rights.licence | Licencia | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) | es |
| dc.subject | Palabras clave | Flow-based model | es |
| dc.subject | Palabras clave | Flexible model | es |
| dc.subject | Palabras clave | Effective optimization | es |
| dc.subject | Palabras clave | Linealization | es |
| dc.subject | Palabras clave | Mixed-integer problem formulation | es |
| dc.subject | Palabras clave | Ford-Fulkerson algorithm | es |
| dc.subject | Palabras clave | Steiner Tree Problem | es |
| dc.subject | Palabras clave | Quality of Service Multicast Tree Problem | es |
| dc.title | Título | A new effective mathematical programming model to design CDN topology | es |
| dc.type | Tipo de documento | Tesis de maestría | es |
| thesis.degree.grantor | Facultad o Servicio que otorga el Título | Universidad de la República (Uruguay). Facultad de Ingeniería | es |
| thesis.degree.name | Título Obtenido | Magíster en Investigación de Operaciones | es |
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| BEN19.pdf | Tesis de maestría | 848.76 KB | Adobe PDF |