HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH SEARCH RESULT		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

Download ALL Selected Citations to Citation Manager

Selected Abstracts

Returned: 1 citations and abstracts. Click on down arrow or scroll to see abstracts.

Miguel F. Anjos, and Anthony Vannelli

Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes
INFORMS Journal on Computing 20: 611-617.

Abstract 1 of 1

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

Department of Management Sciences, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
School of Engineering, University of Guelph, Guelph, Ontario N1G 2W1, Canada
anjos{at}stanfordalumni.org
vannelli{at}uoguelph.ca

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) interactions 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 30 facilities. 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.

Key words: single-row facility layout; space allocation; semidefinite programming; cutting planes; combinatorial optimization
History: received February 2007; revised August 2007; accepted January 2008.

[Reprint (PDF) Version of Anjos and Vannelli]