German Title: Beiträge zum Minimum Linear Arrangement Problem
Preview |
PDF, English
Download (1MB) | Terms of use |
Abstract
The Minimum Linear Arrangement problem (MinLA) consists in finding an ordering of the nodes of a weighted graph, such that the sum of the weighted edge lengths is minimized. We report on the usefulness of a new model within a branch-and-cut-and-price algorithm for solving MinLA problems to optimality. The key idea is to introduce binary variables d_{ijk}, that are equal to 1 if nodes i and j have distance k in the permutation. We present formulations for complete and for sparse graphs and explain the realization of a branch-and-cut-and-price algorithm. Furthermore, its different settings are discussed and evaluated. To the study of the theoretical aspects concerning the MinLA, we contribute a characterization of a relaxation of the corresponding polyeder.
Translation of abstract (German)
Das Minimum Linear Arrangement Problem (MinLA) besteht darin, für einen gewichteten Graphen eine lineare Anordnung der Knoten zu bestimmen, welche die gewichtete Summe der Kantenlängen minimiert. Die vorliegende Arbeit untersucht den Nutzen einer neuen Modelierung im Rahmen eines Branch-and-Cut-and-Price Algorithmus zur optimalen Lösung des MinLA. Den Kern der Modellierung bilden binäre Variablen d_{ijk}, die genau dann den Wert 1 haben, wenn die Knoten i und j in der Permutation die Distanz k haben. Wir präsentieren angepasste Formulierungen für dicht- und dünnbesetzte Graphen und erläutern die Realisierung eines Branch-and-Cut-and-Price Algoritmus. Desweiteren werden die verschiedenen Varianten des Algorithmus diskutiert und evaluiert. Zum Studium der theoretischen Aspekte des MinLA leisten wir einen Beitrag mit der Charakterisierung einer Relaxierung des zugehörigen Polyeders.
Document type: | Dissertation |
---|---|
Supervisor: | Reinelt, Prof. Dr. Gerhard |
Date of thesis defense: | 19 April 2010 |
Date Deposited: | 22 Apr 2010 08:01 |
Date: | 2010 |
Faculties / Institutes: | The Faculty of Mathematics and Computer Science > Department of Computer Science |
DDC-classification: | 510 Mathematics |
Controlled Keywords: | Diskrete Optimierung, Branch-and-Price-Methode, Branch-and-Cut-Methode, Polyedrische Kombinatorik, Polytop, Arrangement |
Uncontrolled Keywords: | Branch-and-Cut-and-Price-Methode , Permutationsproblem , Graph Layout ProblemBranch-and-Cut-and-Price-Method , Permutation problem , Graph Layout Problem |