Optimization Online


A Polyhedral Approach to the Single Row Facility Layout Problem

Adam Letchford (A.N.Letchford***at***lancaster.ac.uk)
Andre Amaral (amaral***at***inf.ufes.br)

Abstract: The Single Row Facility Layout Problem (SRFLP) is the problem of arranging facilities of given lengths on a line, while minimizing a weighted sum of the distances between all pairs of facilities. The SRFLP is strongly NP-hard and includes the well-known linear arrangement problem as a special case. We perform the first ever polyhedral study of the SRFLP. As well as describing several classes of valid and facet-inducing inequalities, we point out an interesting connection to the well-known cut cone. These theoretical results are then used to design a cutting plane algorithm. The computational results are encouraging.

Keywords: facility layout, linear arrangement, polyhedral combinatorics

Category 1: Integer Programming

Category 2: Combinatorial Optimization

Citation: A.R.S. Amaral & A.N. Letchford (2013) A polyhedral approach to the single-row facility layout problem. Math. Program., 141, 453-477.


Entry Submitted: 03/14/2008
Entry Accepted: 03/14/2008
Entry Last Modified: 11/05/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society