Bibliographic Metadata

Title
Nonlinear optimization techniques applied to combinatorial optimization problems / Angelika Wiegele
Additional Titles
Nichtlineare Optimierungsmethoden angewandt auf Probleme der kombinatorischen Optimierung
AuthorWiegele, Angelika
CensorRendl, Franz ; Nowak, Christine
Published2006
DescriptionX, 131 S. : graph. Darst.
Institutional NoteKlagenfurt, Alpen-Adria-Univ., Diss., 2006
Annotation
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
LanguageEnglish
Bibl. ReferenceKB2006 26 ; OeBB
Document typeDissertation (PhD)
Keywords (DE)Semidefinite Programmierung, kombinatorische Optimierung, large-scale Probleme, Bündelmethoden, Max-Cut Problem
Keywords (EN)Semidefinite Programming, Combinatorial Optimization, large-scale problems, bundle-methods, Max-Cut problem
Keywords (GND)Kombinatorische Optimierung / Nichtlineare Optimierung / Maximaler-Schnitt-Problem
URNurn:nbn:at:at-ubk:1-3405 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Nonlinear optimization techniques applied to combinatorial optimization problems [5.67 mb]
Links
Reference
Classification
Abstract (German)

In den letzten beiden Jahrzehnten haben die Forschungsgebiete "Semidefinite Programmierung" und "Kombinatorische Optimierung" die Aufmerksamkeit vieler Forscher aus den Bereichen Mathematik und Informatik auf sich gelenkt. Erstaunliche Fortschritte konnten in diesen beiden Gebieten erzielt weden. Diese Dissertation ist ein weiterer Beitrag zur LÃsung von Problemen der kombinatorischen Optimierung und zur Erforschung der Semidefiniten Programmierung.

Aufgrund der zahlreichen Anwendungen besteht ein groÃes Interesse an der Entwicklung von Algorithmen zur LÃsung Semidefiniter Programme.

ZuverlÃ$ssige und weitverbreitete Algorithmen, wie die Innere-Punkte-Methoden oder die spektrale BÃndelmethode, existieren, doch scheitern diese Methoden oft wenn es darum geht Probleme groÃer Dimension oder mit vielen Nebenbedingungen zu lÃsen, da der Rechen- oder der Speicheraufwand zu groà ist. In dieser Dissertation werden Algorithmen vorgestellt, die in der Lage sind Semidefinite Programme mit groÃer Dimension und vielen Nebenbediungen zu lÃsen.

Diese Methoden sind: die BÃndelmethode zum LÃsen Semidefiniter Programme, die spektrale BÃndel-Methode unter Verwendung von Informationen zweiter Ordnung und die Randpunktemethode.

Die BÃndelmethode ermÃglicht es, Semidefinite Programm zu lÃsen selbst wenn die Anzahl an Nebenbedingungen verhÃ$ltnismÃ$Ãig groà ist. Mit Hilfe von Lagrange-Multiplikatoren werden die Nebenbedingungen in die Zielfunktion aufgenommen und das resultierende duale Problem dann mit dem Konzept der BÃndelmethoden gelÃst.

Die spektrale BÃndelmethode sucht nach dem Minimum des grÃÃten Eigenwertes $\lambda_ Da das Verhalten zweiter Ordnung der $\lambda_ Die Anwendungen des Problems des maximalen Schnittes sind vielfÃ$ltiger als man auf den ersten Blick glaubt, da jedes quadratische (0-1) Problem in ein Problem des maximalen Schnittes transformiert werden kann. Neben der Beschreibung einiger charakteristischer Eigenschaften des Problems und der AufzÃ$hlung der bisher erfolgreichsten LÃsungsmethoden, werden neue Relaxierungen, basierend auf Semidefiniter Progrmmierung, vorgestellt.

Schlussendlich wird "Biq Mac" eingefÃhrt, ein Algorithmus zur exakten LÃsung von maximaler Schnitt Problemen. Biq Mac ist die Implementierung eines Branch & Bound Algorithms' mit einer Boundingroutine basierend auf Semidefiniter Programmierung. Algorithmische Details von Biq Mac und ausfÃhrlich diskutierte numerische Ergebnisse finden sich in der vorliegenden Arbeit. Verschiedenste, seit Jahren betrachtete Testprobleme aus diversen Literaturquellen, wurden mit Hilfe von Biq Mac erstmals gelÃst. Dies ist eine weitere BestÃ$tigung des Erfolges der Anwendung von Semidefiniter Programmierung fÃr Probleme der kombinatorischen Optimierung.

Abstract (English)

Combinatorial Optimization and Semidefinite Programming are two research topics that have attracted the attention of many mathematicians and computer scientists during the past two decades. Remarkable results have been achieved in both fields. This thesis is a further component in exploring the field of Semidefinite Programming and investigating Combinatorial Optimization problems. Due to the various areas of application, one research topic of high interest is the development of algorithms for solving Semidefinite Programs. Although reliable methods are already available and widely used these algorithms are often inapplicable for large-scale programs, due to the huge memory requirements or the vast computational effort. The present work proposes methods (and implementations) that are capable of solving Semidefinite Programs of high dimensions and/or a large number of constraints. These methods are:

the Bundle Method applied to solve Semidefinite Programs, the Spectral Bundle Method with second order information, and the Boundary Point Method.

Exploiting the concept of Bundle Methods allows solving problems, even if the number of constraints is rather large. By the use of Lagrange multipliers, the constraints (or some of them) are lifted into the objective function and the dual problem is then solved following the concept of Bundle Methods.

In the Spectral Bundle Method the largest Eigenvalue $\la_ This is an augmented Lagrangian algorithm applied to solve Semidefinite Programs. For various problem classes this method is by far superior to other available algorithms.

Regarding applications, the main focus of this study is on the Max-Cut problem, one of the most challenging Combinatorial Optimization problems. The applicability of this problem is even broader than obvious at first sight, since any unconstrained quadratic \zeroone problem can be transformed to a Max-Cut problem. Apart from recalling the properties of the problem and giving a survey of relaxations and known solution methods, new relaxations based on Semidefinite Programming are introduced. Finally, "Biq Mac" was developed, a solver for binary quadratic and Max-Cut problems. Biq Mac is an implementation of an exact solution method using a Branch & Bound algorithm with a bounding routine based on Semidefinite Programming. Detailed information on this algorithm, as well as a collection of test problems together with numerical results, can be found in the present thesis. Various test problems that have been considered in the literature for years, were solved by Biq Mac for the first time. This affirms the success of using Semidefinite Programming for Combinatorial Optimization problems.

Stats
The PDF-Document has been downloaded 15 times.