A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

0.00 Avg rating0 Votes
Article ID: iaor200971531
Country: Germany
Volume: 3
Issue: 4
Start Page Number: 513
End Page Number: 520
Publication Date: Sep 2009
Journal: Optimization Letters
Authors:
Keywords: programming: integer
Abstract:

We are concerned with the exact solution of a graph optimization problem known as minimum linear arrangement (MinLA). Define the length of each edge of a graph with respect to a linear ordering of the graph vertices. Then, the MinLA problem asks for a vertex ordering that minimizes the sum of edge lengths. MinLA has several practical applications and is NP-Hard. We present a mixed 0-1 linear programming formulation of the problem, which led to fast optimal solutions for dense graphs of sizes up to n = 23.

Reviews

Required fields are marked *. Your email address will not be published.