A polyhedral study of triplet formulation for single row facility layout problem
The single row facility layout problem (SRFLP) is the problem of arranging n n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183190]. For any number of departments n n , we prove that the dimension of the triplet polytope is n(n?1)(n?2)/3 n ( n ? 1 ) ( n ? 2 ) / 3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.
single row facility layout problem valid inequality linear arrangement polyhedron facet