Dokument: On the depth of the Branch and Bound tree for solving the Maximum Stable Set Problem

Titel:	On the depth of the Branch and Bound tree for solving the Maximum Stable Set Problem
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=44817
URN (NBN):	urn:nbn:de:hbz:061-20180208-110943-4
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	MS.C. Baniasadirad, Fatemeh [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 485,1 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 06.02.2018 / geändert 06.02.2018
Beitragende:	Prof. Dr. Jarre, Florian [Betreuer/Doktorvater] Prof. Dr. Schädle, Achim [Gutachter]
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibung:	Motivated by the recent progress in the solution of large scale semidefinite programs, in particular with the program package SDPNAL [35], this thesis investigates in how far semidefinite programs can be used in a branch and bound approach for solving the maximum stable set problem. Chapter 2 provides an introduction to semidefinite programs. Chapter 3 briefly describes how SDPNAL solves semidefinite programs. Lemma 7, the proof of Lemma 8, Remark 2 and Example 2 are the main contributions of this chapter. The maximum stable set problem and some known facts are presented in Chapter 4. Classical relaxations for the maximum stable set problem are the Lovasz ⍬-number (4.8) and the Lovasz-Schrijver ⍬-number (4.9). We recall some well known alternative relaxations. In Theorem 10, based on the proof of M. Laurent [20], the proof of equivalency of two such formulations (4.6) and (4.8) is extended to the doubly nonnegative cone. Theorem 9 presents a new proof for the relation of (4.6) with another relaxation (4.7). A new relaxation of (4.7) is introduced in problem (4.18). According to Proposition 3, all semidefinite relaxations in this chapter are mathematically equivalent. A numerical comparison of them given in Table 4.1 is intended to illustrate possible rounding errors associated with the approximate solution generated by SDPNAL. The last discussion of this chapter is concerned with the computation a valid upper bound on the optimal value of a primal semidefinite program from an approximate solution under generic nondegeneracy conditions. The last four chapters present and analyze the branch and bound strategy to solve the maximum stable set problem. At each level of branching a series of semidefinite relaxations is solved providing a valid upper bound to the stable set problem. We complement the semidefinite upper bound by modifying a randomized approach (due to Goemans and Williamson) to generate feasible and locally optimal solutions to the stable set problem. We show (Proposition 1) that the distribution for generating the approximate solution to the maximum stable set problem is not dependent on the factorization of the optimal solution of the semidefinite relaxation. The main contributions of these chapters are listed as follows: 1. To avoid inaccurate results caused by rounding errors and truncation errors in the solution generated by SDPNAL, we propose a practical method applied to an approximate solution of the Lovasz-Schrijver number (4.9). The method provides a reliable upper bound on the stable set problem. 2. We develop a new approach for estimating the stability number of a given graph (Section 6.1). To apply this method, we assume that an upper bound on the stable set problem is known. We introduce a random f0; 1g-vector and solve a number of relaxations (4.6) for a graph defined via the {0.1}-vector. Three di_erent strategies are presented to construct a random {0.1}-vector with the goal of reducing the dimension of the relaxations (4.6) (Section 6.1.1). 3. Another approach contributed in this thesis is adding additional constraints to the relaxation (4.6) to strengthen the upper bound on the stable set problem and to provide a new branching strategy. We discuss how to determine the data of the new additional constraint to provide a deep cut (Section 6.3). We also address how to prove the infeasibility of the new relaxation in the presence of rounding errors (Section 6.4). 4. We discuss the relation between the algorithm proposed in this dissertation and the one proposed by Benson and Ye through Corollary 1 and Remark 14. Lemma 12 (not proven by Benson and Ye) determines the Lovasz-number of the Benson-Ye-approach. The last chapter gives some insight about the practical behavior of a branch and bound approach.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät
Dokument erstellt am:	08.02.2018
Dateien geändert am:	08.02.2018
Promotionsantrag am:	05.02.2017
Datum der Promotion:	01.06.2017