On a binary distance model for the minimum linear arrangement problem

Gerhard Reinelt ^[1] ; Hanna Seitz ^[1]
1. [1] Universität Heidelberg, Alemania
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 22, Nº. 1, 2014, págs. 384-396
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- The minimum linear arrangement problem consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. The problem is among the classical NP-hard optimization problems and there has been extensive research on exact and approximative algorithms. In this paper, we introduce a new model based on binary variables d ijk that are equal to 1 if nodes i and j have distance k in the ordering. We analyze this model and point to connections and differences to a model using integer distance variables. Based on computational experiments, we argue that our model is worth further theoretical and practical investigation and that is has potentials yet to be examined.