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

Vorschau

PDF, Englisch Download (1MB) | Nutzungsbedingungen

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.