On a binary distance model for the minimum linear arrangement problem

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...

Full description

Saved in:
Bibliographic Details
Published in:TOP 2014-04, Vol.22 (1), p.384-396
Main Authors: Reinelt, Gerhard, Seitz, Hanna
Format: Article
Language:English
Subjects:
Business and Management
Economic Theory/Quantitative Economics/Mathematical Methods
Economics
Finance
Industrial and Production Engineering
Insurance
Management
Operations Research/Decision Theory
Optimization
Original Paper
Statistics for Business
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1134-5764
1863-8279
DOI:10.1007/s11750-012-0263-7