Contributions to the Minimum Linear Arrangement Problem

The Minimum Linear Arrangement problem 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 Minimum Linear Arrangement 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 Minimum Linear Arrangement problem, we contribute a characterization of a relaxation of the corresponding polyeder.

Autorentext

Hanna Seitz studied mathematics in Heidelberg, Germany, and received a scholarship of the German National Academic Foundation (Studienstiftung). She completed her Doctorate in Natural Sciences in the field of discrete and combinatorial optimization at the Ruprecht Karl University of Heidelberg in 2010.