GRASP/VND Optimization Algorithms for Hard Combinatorial Problems
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...
Sábháilte in:
| Príomhchruthaitheoir: | |
|---|---|
| Formáid: | doctoralThesis |
| Teanga: | Béarla |
| Foilsithe / Cruthaithe: |
2019
|
| Ábhair: | |
| Rochtain ar líne: | https://hdl.handle.net/20.500.12008/34293 |
| Clibeanna: |
Níl clibeanna ann, Bí ar an gcéad duine le clib a chur leis an taifead seo!
|
| _version_ | 1868890232944852992 |
|---|---|
| author | Stabile Suárez, Luis Alberto |
| author_browse | Stabile Suárez, Luis Alberto |
| author_facet | Stabile Suárez, Luis Alberto |
| author_role | author |
| collection | COLIBRI |
| dc.contributor.none.fl_str_mv | Stabile Suárez Luis Alberto, Universidad de la República (Uruguay). Facultad de Ingeniería |
| dc.creator.none.fl_str_mv | Stabile Suárez, Luis Alberto |
| dc.date.none.fl_str_mv | 2019 2022-10-24T15:59:04Z 2022-10-24T15:59:04Z |
| dc.format.none.fl_str_mv | 119 p. application/pdf |
| dc.identifier.none.fl_str_mv | Stabile Suárez, L. GRASP/VND Optimization Algorithms for Hard Combinatorial Problems [en línea] Tesis de doctorado. Montevideo : Udelar. FI. INCO : PEDECIBA, 2019. 1688-2776 https://hdl.handle.net/20.500.12008/34293 |
| dc.language.none.fl_str_mv | en eng |
| dc.publisher.none.fl_str_mv | Udelar.FI |
| dc.rights.none.fl_str_mv | info:eu-repo/semantics/openAccess Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| dc.source.none.fl_str_mv | reponame:COLIBRI instname:Universidad de la República instacron:Universidad de la República |
| dc.subject.none.fl_str_mv | Max Cut-Clique Uniformly Most-Reliable Graph Stochastic Binary System GRASP VND |
| dc.title.none.fl_str_mv | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| dc.type.none.fl_str_mv | Tesis de doctorado info:eu-repo/semantics/doctoralThesis info:eu-repo/semantics/acceptedVersion |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | doctoralThesis |
| id | anni_f3acddf79b33e205f90d7b54bd4d37bb |
| identifier_str_mv | Stabile Suárez, L. GRASP/VND Optimization Algorithms for Hard Combinatorial Problems [en línea] Tesis de doctorado. Montevideo : Udelar. FI. INCO : PEDECIBA, 2019. 1688-2776 |
| instacron_str | Universidad de la República |
| institution | Universidad de la República |
| instname_str | Universidad de la República |
| language | eng |
| language_invalid_str_mv | en |
| network_acronym_str | anni |
| network_name_str | oai-lr-anni |
| oai_identifier_str | oai:colibri.udelar.edu.uy:20.500.12008/34293 |
| publishDate | 2019 |
| publishDateSort | 2019 |
| publisher.none.fl_str_mv | Udelar.FI |
| reponame_str | COLIBRI |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| spelling | GRASP/VND Optimization Algorithms for Hard Combinatorial ProblemsStabile Suárez, Luis AlbertoMax Cut-CliqueUniformly Most-Reliable GraphStochastic Binary SystemGRASPVNDTwo 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.Udelar.FIStabile Suárez Luis Alberto, Universidad de la República (Uruguay). Facultad de Ingeniería2022-10-24T15:59:04Z2022-10-24T15:59:04Z2019Tesis de doctoradoinfo:eu-repo/semantics/doctoralThesisinfo:eu-repo/semantics/acceptedVersion119 p.application/pdfStabile Suárez, L. GRASP/VND Optimization Algorithms for Hard Combinatorial Problems [en línea] Tesis de doctorado. Montevideo : Udelar. FI. INCO : PEDECIBA, 2019.1688-2776https://hdl.handle.net/20.500.12008/34293reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicaenengLas 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)info:eu-repo/semantics/openAccessLicencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)oai:colibri.udelar.edu.uy:20.500.12008/342932026-04-14T10:27:57Z |
| spellingShingle | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems Stabile Suárez, Luis Alberto Max Cut-Clique Uniformly Most-Reliable Graph Stochastic Binary System GRASP VND |
| status_str | acceptedVersion |
| title | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| title_full | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| title_fullStr | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| title_full_unstemmed | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| title_short | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| title_sort | GRASP/VND Optimization Algorithms for Hard Combinatorial Problems |
| topic | Max Cut-Clique Uniformly Most-Reliable Graph Stochastic Binary System GRASP VND |
| url | https://hdl.handle.net/20.500.12008/34293 |