Optimization Online


A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem

Sujeevraja Sanjeevi (sujeevraja***at***neo.tamu.edu)
Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: 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 [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.

Keywords: single row facility layout problem, linear arrangement, polyhedron, valid inequality, facet

Category 1: Integer Programming

Citation: Department of Industrial and Systems Engineering, Texas A&M University, College Station, TX USA 77843-3131, February 2010


Entry Submitted: 04/01/2010
Entry Accepted: 04/06/2010
Entry Last Modified: 03/13/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society