A Polyhedral Approach to the Single Row Facility Layout Problem
Adam Letchford (A.N.Letchfordlancaster.ac.uk)
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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|