A polyhedral study of triplet formulation for single row facility layout problem

作者：Sanjeevi Sujeevraja^*; Kianfar Kiavash

来源：Discrete Applied Mathematics, 2010, 158(16): 1861-1867.

DOI：10.1016/j.dam.2010.07.005

• Single row facility layout problem
• Linear arrangement
• Polyhedron
• Valid inequality
• Facet

The single row facility layout problem (SRFLP) is the problem of arranging 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 [ARS. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1)(2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is 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.

• 出版日期2010-8-28