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.

Contributions to the Minimum Linear Arrangement Problem

Seitz, Hanna

Deutsche Übersetzung des Titels: Beiträge zum Minimum Linear Arrangement Problem

[thumbnail of MinLA_Thesis_Seitz.pdf]
Vorschau
PDF, Englisch
Download (1MB) | 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 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.

Übersetzung des Abstracts (Deutsch)

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.

Dokumententyp: Dissertation
Erstgutachter: Reinelt, Prof. Dr. Gerhard
Tag der Prüfung: 19 April 2010
Erstellungsdatum: 22 Apr. 2010 08:01
Erscheinungsjahr: 2010
Institute/Einrichtungen: Fakultät für Mathematik und Informatik > Institut für Informatik
DDC-Sachgruppe: 510 Mathematik
Normierte Schlagwörter: Diskrete Optimierung, Branch-and-Price-Methode, Branch-and-Cut-Methode, Polyedrische Kombinatorik, Polytop, Arrangement
Freie Schlagwörter: Branch-and-Cut-and-Price-Methode , Permutationsproblem , Graph Layout ProblemBranch-and-Cut-and-Price-Method , Permutation problem , Graph Layout Problem
Leitlinien | Häufige Fragen | Kontakt | Impressum |
OA-LogoDINI-Zertifikat 2013Logo der Open-Archives-Initiative