english Icono del idioma   español Icono del idioma  

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12008/34293 How cite
Title: GRASP/VND Optimization Algorithms for Hard Combinatorial Problems
Authors: Stabile Suárez, Luis Alberto
Obtained title: Doctor en Informática
University or service that grants the title: Universidad de la República (Uruguay). Facultad de Ingeniería
Tutor: Robledo, Franco
Romero, Pablo
Bourel, Mathias
Type: Tesis de doctorado
Keywords: Max Cut-Clique, Uniformly Most-Reliable Graph, Stochastic Binary System, GRASP, VND
Issue Date: 2019
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.
Publisher: Udelar.FI
ISSN: 1688-2776
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.
License: Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Appears in Collections:Tesis de posgrado - Instituto de Computación

Files in This Item:
File Description SizeFormat  
Sta19.pdfTesis de Doctorado2,62 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons