A Polyhedral Approach to the Single Row Facility Layout Problem

Adam Letchford (A.N.Letchfordlancaster.ac.uk)
Andre Amaral (amaralinf.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: Working paper, Department of Management Science, Lancaster University, March 2008

Download: [PDF]

Entry Submitted: 03/14/2008
Entry Accepted: 03/14/2008
Entry Last Modified: 02/10/2011

Modify/Update this entry