×

Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. (English) Zbl 1243.90174

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.

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

Software:

LOLIB; CSDP; ATLAS
PDFBibTeX XMLCite
Full Text: DOI