Given a graph G=(V,E) on n vertices, the Minimum Linear Arrangement Problem (MinLA) calls for a one-to-one function ψ : V -> {1,...,n} which minimizes ∑{|ψ(i)−ψ(j)| : {i,j} in E}. MinLA is strongly -hard and very difficult to solve to optimality in practice. One of the reasons for this difficulty is the lack of good lower bounds. In this paper, we take a polyhedral approach to MinLA. We associate an integer polyhedron with each graph G, and derive many classes of valid linear inequalities. It is shown that a cutting plane algorithm based on these inequalities can yield competitive lower bounds in a reasonable amount of time. A key to the success of our approach is that our linear programs contain only E variables. We conclude showing computational results on benchmark graphs from literature.

A New Lower Bound for the Minimum Linear Arrangement of a Graph

CAPRARA, ALBERTO;
2008

Abstract

Given a graph G=(V,E) on n vertices, the Minimum Linear Arrangement Problem (MinLA) calls for a one-to-one function ψ : V -> {1,...,n} which minimizes ∑{|ψ(i)−ψ(j)| : {i,j} in E}. MinLA is strongly -hard and very difficult to solve to optimality in practice. One of the reasons for this difficulty is the lack of good lower bounds. In this paper, we take a polyhedral approach to MinLA. We associate an integer polyhedron with each graph G, and derive many classes of valid linear inequalities. It is shown that a cutting plane algorithm based on these inequalities can yield competitive lower bounds in a reasonable amount of time. A key to the success of our approach is that our linear programs contain only E variables. We conclude showing computational results on benchmark graphs from literature.
A.R.S. Amaral; A. Caprara; A.N. Letchford; J.J. Salazar
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/66497
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact