Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Contributions to the Minimum Linear Arrangement Problem

Seitz, Hanna

German Title: Beiträge zum Minimum Linear Arrangement Problem

[img]
Preview
PDF, English
Download (1653Kb) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the persistent URL or the URN below, as we can guarantee their long-time accessibility.

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.

Item 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
Subjects: 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
About | FAQ | Contact | Imprint |
OA-LogoLogo der Open-Archives-Initiative