english Icono del idioma   español Icono del idioma  

Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/20.500.12008/34293 Cómo citar
Título: GRASP/VND Optimization Algorithms for Hard Combinatorial Problems
Autor: Stabile Suárez, Luis Alberto
Título Obtenido: Doctor en Informática
Facultad o Servicio que otorga el Título: Universidad de la República (Uruguay). Facultad de Ingeniería
Tutor: Robledo, Franco
Romero, Pablo
Bourel, Mathias
Tipo: Tesis de doctorado
Palabras clave: Max Cut-Clique, Uniformly Most-Reliable Graph, Stochastic Binary System, GRASP, VND
Fecha de publicación: 2019
Resumen: 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.
Editorial: Udelar.FI
ISSN: 1688-2776
Citación: Stabile Suárez, L. GRASP/VND Optimization Algorithms for Hard Combinatorial Problems [en línea] Tesis de doctorado. Montevideo : Udelar. FI. INCO : PEDECIBA, 2019.
Licencia: Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Aparece en las colecciones: Tesis de posgrado - Instituto de Computación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato   
Sta19.pdfTesis de Doctorado2,62 MBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons