Optimization Online


Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes

Miguel F. Anjos(anjos***at***stanfordalumni.org)
Anthony Vannelli(vannelli***at***uoguelph.ca)

Abstract: This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to thirty departments. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988.

Keywords: single-row facility layout, space allocation, semidefinite programming, cutting planes, combinatorial 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: To appear in INFORMS Journal on Computing, 2008.

Download: [PDF]

Entry Submitted: 01/27/2008
Entry Accepted: 01/28/2008
Entry Last Modified: 01/27/2008

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