%0 Generic
%A Seitz, Hanna
%D 2010
%F heidok:10578
%K Branch-and-Cut-and-Price-Methode , Permutationsproblem , Graph Layout ProblemBranch-and-Cut-and-Price-Method , Permutation problem , Graph Layout Problem
%R 10.11588/heidok.00010578
%T Contributions to the Minimum Linear Arrangement Problem
%U https://archiv.ub.uni-heidelberg.de/volltextserver/10578/
%X 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.