Optimization Online


A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions

Miguel F. Anjos (anjos***at***stanfordalumni.org)
Andrew Kennings (akenning***at***cheetah.vlsi.uwaterloo.ca)
Anthony Vannelli (vannelli***at***cheetah.vlsi.uwaterloo.ca)

Abstract: The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear placement of facilities with varying dimensions on a straight line. We construct a semidefinite programming (SDP) relaxation providing a lower bound on the optimal value of the ODSAP. To the best of our knowledge, this is the first non-trivial global lower bound for the ODSAP in the published literature. This SDP approach implicitly takes into account the natural symmetry of the problem and, unlike other algorithms in the literature, does not require the use of any explicit symmetry-breaking constraints. Furthermore, the structure of the SDP relaxation suggests a simple heuristic procedure which extracts a feasible solution to the ODSAP from the optimal matrix solution to the SDP relaxation. Computational results show that this heuristic yields a solution which is consistently within a few percentage points of the global optimal solution.

Keywords: Facilities planning and design, Space Allocation,Combinatorial Optimization,Semidefinite Optimization, Global Optimization.

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

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Category 3: Applications -- Science and Engineering (VLSI layout )

Citation: Discrete Optimization, Vol. 2(2), 113-122, 2005.


Entry Submitted: 03/31/2005
Entry Accepted: 03/31/2005
Entry Last Modified: 07/23/2005

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