Por favor, use este identificador para citar o enlazar este ítem:
https://hdl.handle.net/20.500.12008/34293
Cómo citar
Registro completo de metadatos
Campo DC | Valor | Lengua/Idioma |
---|---|---|
dc.contributor.advisor | Robledo, Franco | - |
dc.contributor.advisor | Romero, Pablo | - |
dc.contributor.advisor | Bourel, Mathias | - |
dc.contributor.author | Stabile Suárez, Luis Alberto | - |
dc.date.accessioned | 2022-10-24T15:59:04Z | - |
dc.date.available | 2022-10-24T15:59:04Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Stabile Suárez, L. GRASP/VND Optimization Algorithms for Hard Combinatorial Problems [en línea] Tesis de doctorado. Montevideo : Udelar. FI. INCO : PEDECIBA, 2019. | es |
dc.identifier.issn | 1688-2776 | - |
dc.identifier.uri | https://hdl.handle.net/20.500.12008/34293 | - |
dc.description.abstract | Two hard combinatorial problems are addressed in this thesis. The first one is known as the ”Max CutClique”, a combinatorial problem introduced by P. Martins in 2012. Given a simple graph, the goal is to find a clique C such that the number of links shared between C and its complement C C is maximum. In a first contribution, a GRASP/VND methodology is proposed to tackle the problem. In a second one, the N P-Completeness of the problem is mathematically proved. Finally, a further generalization with weighted links is formally presented with a mathematical programming formulation, and the previous GRASP is adapted to the new problem. The second problem under study is a celebrated optimization problem coming from network reliability analysis. We assume a graph G with perfect nodes and imperfect links, that fail independently with identical probability ρ ∈ [0,1]. The reliability RG(ρ), is the probability that the resulting subgraph has some spanning tree. Given a number of nodes and links, p and q, the goal is to find the (p,q)-graph that has the maximum reliability RG(ρ), uniformly in the compact set ρ ∈ [0,1]. In a first contribution, we exploit properties shared by all uniformly most-reliable graphs such as maximum connectivity and maximum Kirchhoff number, in order to build a novel GRASP/VND methodology. Our proposal finds the globally optimum solution under small cases, and it returns novel candidates of uniformly most-reliable graphs, such as Kantor-Mobius and Heawood graphs. We also offer a literature review, ¨ and a mathematical proof that the bipartite graph K4,4 is uniformly most-reliable. Finally, an abstract mathematical model of Stochastic Binary Systems (SBS) is also studied. It is a further generalization of network reliability models, where failures are modelled by a general logical function. A geometrical approximation of a logical function is offered, as well as a novel method to find reliability bounds for general SBS. This bounding method combines an algebraic duality, Markov inequality and Hahn-Banach separation theorem between convex and compact sets. | es |
dc.format.extent | 119 p. | es |
dc.format.mimetype | application/pdf | es |
dc.language.iso | en | es |
dc.publisher | Udelar.FI | es |
dc.rights | 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.subject | Max Cut-Clique | es |
dc.subject | Uniformly Most-Reliable Graph | es |
dc.subject | Stochastic Binary System | es |
dc.subject | GRASP | es |
dc.subject | VND | es |
dc.title | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems | es |
dc.type | Tesis de doctorado | es |
dc.contributor.filiacion | Stabile Suárez Luis Alberto, Universidad de la República (Uruguay). Facultad de Ingeniería | - |
thesis.degree.grantor | Universidad de la República (Uruguay). Facultad de Ingeniería | es |
thesis.degree.name | Doctor en Informática | es |
dc.rights.licence | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) | es |
Aparece en las colecciones: | Tesis de posgrado - Instituto de Computación |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | ||
---|---|---|---|---|---|
Sta19.pdf | Tesis de Doctorado | 2,62 MB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons