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.
Citation
A.R.S. Amaral & A.N. Letchford (2013) A polyhedral approach to the single-row facility layout problem. Math. Program., 141, 453-477.