Direkt zum Inhalt
  1. Publizieren |
  2. Suche |
  3. Browsen |
  4. Neuzugänge rss |
  5. Open Access |
  6. Rechtsfragen |
  7. EnglishCookie löschen - von nun an wird die Spracheinstellung Ihres Browsers verwendet.

Contraction-based Separation and Lifting for Solving the Max-Cut Problem

Bonato, Thorsten

Deutsche Übersetzung des Titels: Kontraktionsbasierte Separierung und Liftung zur Lösung des Max-Cut-Problems

[thumbnail of MaxCut_Thesis_Bonato.pdf]
Vorschau
PDF, Englisch
Download (978kB) | Nutzungsbedingungen

Zitieren von Dokumenten: Bitte verwenden Sie für Zitate nicht die URL in der Adresszeile Ihres Webbrowsers, sondern entweder die angegebene DOI, URN oder die persistente URL, deren langfristige Verfügbarkeit wir garantieren. [mehr ...]

Abstract

The max-cut problem is an NP-hard combinatorial optimization problem defined on undirected weighted graphs. It consists in finding a subset of the graph's nodes such that the aggregate weight of the edges between the subset and its complement is maximized. In this doctoral thesis we present a new separation approach to be used within a branch-and-cut algorithm for solving max-cut problems to optimality. This method is based on graph contraction and allows the fast separation of so-called odd-cycle inequalities. In addition, we describe techniques to add possibly missing edges to an already contracted graph. This allows solving max-cut problems on sparse graphs by using methods that were originally intended for complete graphs and could not have been applied otherwise. We investigate the theoretical aspects of this combined approach and also explain its realization within a branch-and-cut framework. Finally, we evaluate the performance of our separation procedure on a variety of test instances.

Übersetzung des Abstracts (Deutsch)

Das Max-Cut-Problem ist ein auf ungerichteten gewichteten Graphen definiertes NP-schweres kombinatorisches Optimierungsproblem. Es besteht darin, eine Teilmenge der Knoten des Graphen zu bestimmen, so dass das summierte Gewicht der Kanten zwischen der Teilmenge und ihrem Komplement maximiert wird. In der vorliegenden Arbeit stellen wir einen neuen Separierungsansatz vor, der im Rahmen eines Branch-and-Cut-Algorithmus verwendet werden kann, um Max-Cut-Probleme optimal zu lösen. Die Methode basiert auf der Kontraktion des Graphen und erlaubt die effiziente Separierung sogenannter Ungerader-Kreis-Ungleichungen. Darüber hinaus beschreiben wir Techniken, um im bereits kontrahierten Graphen gegebenenfalls fehlende Kanten hinzuzufügen. Dies ermöglicht es, Max-Cut-Probleme auf dünn besetzten Graphen unter Verwendung von Methoden für vollständige Graphen zu lösen, die ansonsten nicht anwendbar gewesen wären. Wir untersuchen die theoretischen Aspekte dieses kombinierten Ansatzes und erläutern seine Umsetzung innerhalb eines Branch-and-Cut-Systems. Abschließend bewerten wir die Leistungsfähigkeit unserer Separierungsroutine anhand einer Vielzahl unterschiedlicher Testinstanzen.

Dokumententyp: Dissertation
Erstgutachter: Reinelt, Prof. Dr. Gerhard
Tag der Prüfung: 14 Juni 2011
Erstellungsdatum: 25 Jul. 2011 13:45
Erscheinungsjahr: 2011
Institute/Einrichtungen: Fakultät für Mathematik und Informatik > Institut für Informatik
DDC-Sachgruppe: 510 Mathematik
Normierte Schlagwörter: Kombinatorische Optimierung, Maximaler-Schnitt-Problem, Konvexes Polytop, Branch-and-Cut-Methode
Freie Schlagwörter: Max-Cut-Problem , Cut-Polytop , SeparierungCombinatorial optimization , Max-Cut problem , Cut polytope , Separation , Branch-and-Cut method
Leitlinien | Häufige Fragen | Kontakt | Impressum |
OA-LogoDINI-Zertifikat 2013Logo der Open-Archives-Initiative