GRASP/VND Optimization Algorithms for Hard Combinatorial Problems

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.