Optimization Online


Provably Near-Optimal Solutions for Very Large Single-Row Facility Layout Problems

Miguel F. Anjos(anjos***at***stanfordalumni.org)
Ginger Yen(tyen***at***engmail.uwaterloo.ca)

Abstract: The facility layout problem is a global optimization problem that seeks to arrange a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. This paper is concerned with the single-row facility layout problem (SRFLP), the one-dimensional version of facility layout that is also known as the one-dimensional space allocation problem. It was recently shown that the combination of a semidefinite programming (SDP) relaxation with cutting planes is able to compute globally optimal layouts for SRFLPs with up to 30 facilities. This paper further explores the application of SDP to this problem. First, we revisit the recently proposed quadratic formulation of this problem that underlies the SDP relaxation and provide an independent proof that the feasible set of the formulation is a precise representation of the set of all permutations on $n$ objects. This fact follows from earlier work of Murata et al., but a proof in terms of the variables and structure of the SDP construction provides interesting insights on our approach. Second, we propose a new matrix-based formulation that yields a new SDP relaxation with fewer linear constraints but still yielding high-quality global lower bounds. Using this new relaxation, we are able to compute nearly-optimal solutions for instances with up to 100 facilities.

Keywords: Single-row Facility Layout, Space Allocation, Combinatorial Optimization, Semidefinite Optimization, Global Optimization.

Category 1: Global Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- Science and Engineering

Citation: To appear in Optimization Methods and Software (accepted March 2009).

Download: [PDF]

Entry Submitted: 03/20/2009
Entry Accepted: 03/25/2009
Entry Last Modified: 03/20/2009

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