Anjos, Miguel F.; Vannelli, Anthony Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. (English) Zbl 1243.90174 INFORMS J. Comput. 20, No. 4, 611-617 (2008). Summary: 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. Cited in 37 Documents MSC: 90C26 Nonconvex programming, global optimization 90B80 Discrete location and assignment 90C27 Combinatorial optimization 90B22 Queues and service in operations research 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:single-row facility layout; space allocation; semidefinite programming Software:LOLIB; CSDP; ATLAS PDFBibTeX XMLCite \textit{M. F. Anjos} and \textit{A. Vannelli}, INFORMS J. Comput. 20, No. 4, 611--617 (2008; Zbl 1243.90174) Full Text: DOI