Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes
Miguel F. Anjos(anjosstanfordalumni.org)
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.
Entry Submitted: 01/27/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|