• search hit 10 of 16
Back to Result List

New Concise Extended Formulations for Circular Structures in Optimization Problems

  • Many NP-hard optimization problems that originate from classical graph theory, such as the maximum stable set problem and the maximum clique problem, have been extensively studied over the past decades and involve the choice of a subset of edges or vertices. There usually exist combinatorial methods that can be applied to solve them directly in the graph. The most simple method is to enumerate feasible solutions and select the best. It is not surprising that this method is very slow oftentimes, so the task is to cleverly discard fruitless search space during the search. An alternative method to solve graph problems is to formulate integer linear programs, such that their solution yields an optimal solution to the original optimization problem in the graph. In order to solve integer linear programs, one can start with relaxing the integer constraints and then try to find inequalities for cutting off fractional extreme points. In the best case, it would be possible to describe the convex hull of the feasible region of the integer linear program with a set of inequalities. In general, giving a complete description of this convex hull is out of reach, even if it has a polynomial number of facets. Thus, one tries to strengthen the (weak) relaxation of the integer linear program best possible via strong inequalities that are valid for the convex hull of feasible integer points. Many classes of valid inequalities are of exponential size. For instance, a graph can have exponentially many odd cycles in general and therefore the number of odd cycle inequalities for the maximum stable set problem is exponential. It is sometimes possible to check in polynomial time if some given point violates any of the exponentially many inequalities. This is indeed the case for the odd cycle inequalities for the maximum stable set problem. If a polynomial time separation algorithm is known, there exists a formulation of polynomial size that contains a given point if and only if it does not violate one of the (potentially exponentially many) inequalities. This thesis can be divided into two parts. The first part is the main part and it contains various new results. We present new extended formulations for several optimization problems, i.e. the maximum stable set problem, the nonconvex quadratic program with box constraints and the p-median problem. In the second part we modify a very fast algorithm for finding a maximum clique in very large sparse graphs. We suggest and compare three alternative versions of this algorithm to the original version and compare their strengths and weaknesses.
  • Viele NP-schwere Optimierungsprobleme aus der klassischen Graphentheorie, wie beispielsweise das Stabile-Mengen-Problem oder das Cliquenproblem, wurden in den vergangenen Jahrzehnten ausgiebig erforscht. Häufig besteht die Problemstellung darin, eine optimale Teilmenge der Knoten oder Kanten des zugrunde liegenden Graphen auszuwählen. Zur Lösung werden in der Regel direkte kombinatorische Methoden auf den Graphen angewandt. Eine universelle und sehr einfache Methode ist die vollständige Enumeration. Alle zulässigen Lösungen werden dabei aufgelistet und die beste davon wird schlussendlich ausgewählt. Aufgrund der meist großen Anzahl an zulässigen Lösungen kann dieses Verfahren durch geschicktes Ausschließen bestimmter Suchbereiche während der Ausführung häufig erheblich beschleunigt werden. Alternativ können graphentheoretische Probleme auch als ganzzahlige lineare Programme formuliert werden, deren optimale Lösung dann eine optimale Lösung für das ursprüngliche Problem liefert. Um ein ganzzahliges lineares Programm zu lösen, lassen sich zunächst die Ganzzahligkeitsbedingungen relaxieren. Anschließend werden Ungleichungen gesucht, welche fraktionale Ecken des für die Relaxierung zulässigen Bereichs, aber keine ganzzahligen Punkte abschneiden. Im Idealfall führt dies zu einer vollständigen Beschreibung der konvexen Hülle aller zulässigen Punkte des ganzzahligen linearen Programms. Leider ist das Finden einer vollständigen Beschreibung selbst für den Fall, dass die entsprechende konvexe Hülle lediglich polynomiell viele Facetten hat, meist viel zu aufwendig. Daraus ergibt sich das Ziel, die schwache Relaxierung des ganzzahligen linearen Programms durch das Hinzufügen starker, für die konvexe Hülle aller ganzzahligen zulässigen Punkte gültiger Ungleichungen bestmöglich zu verstärken. Viele Klassen gültiger Ungleichungen sind exponentiell groß. Ein einfaches Beispiel hierfür sind die ungeraden Kreisungleichungen des Stabile-Mengen-Problems, da ein Graph exponentiell viele ungerade Kreise enthalten kann. Glücklicherweise lässt sich manchmal in polynomieller Zeit überprüfen, ob ein gegebener Punkt mindestens eine von exponentiell vielen Ungleichungen verletzt. Dies ist beispielsweise für die ungeraden Kreisungleichungen des Stabile-Mengen-Problems der Fall. Ein solches Verfahren wird Separations-Algorithmus genannt. Existiert ein solcher, so existiert auch eine lineare Formulierung, die einen bestimmten Punkt genau dann enthält, wenn dieser keine der entsprechenden Ungleichungen verletzt. Diese Arbeit lässt sich inhaltlich in zwei Abschnitte unterteilen, wobei der erste Abschnitt den größten Teil dieser Arbeit bildet. Darin werden insbesondere neue erweiterte Formulierungen für das Stabile-Mengen-Problem, für das allgemeine nichtkonvexe quadratische Programm mit Box-Bedingungen, sowie für das p-Median-Problem vorgestellt. Der zweite Abschnitt dieser Arbeit widmet sich einem bekannten, sehr schnellen Algorithmus zum Finden einer größten Clique in sehr großen, dünn besetzten Graphen. Drei modifizierte Versionen dieses Verfahrens werden hergeleitet und anhand numerischer Experimente mit dem ursprünglichen Algorithmus verglichen.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Bernd Perscheid
URN:urn:nbn:de:hbz:385-1-14788
DOI:https://doi.org/10.25353/ubtr-xxxx-f89c-5538
Referee:Sven de Vries, Eddie Cheng
Advisor:Sven de Vries
Document Type:Doctoral Thesis
Language:English
Date of completion:2020/10/01
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2020/09/09
Release Date:2020/10/13
Tag:Discrete Optimization, Linear Programming, Integer Programming, Extended Formulation, Graph Theory, Branch & Bound
Institutes:Fachbereich 4
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoCC BY: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $