  


A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem
Sujeevraja Sanjeevi (sujeevrajaneo.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)183190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n1)(n2)/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 facetdefining. 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 778433131, February 2010 Download: Entry Submitted: 04/01/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  