Provably near-optimal solutions for very large single-row facility layout problems

Abstract

The facility layout problem is a global optimization problem that seeks to arrange a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. This paper is concerned with the single-row facility layout problem (SRFLP), the one-dimensional version of facility layout that is also known as the one-dimensional space allocation problem. It was recently shown that the combination of a semidefinite programming (SDP) relaxation with cutting planes is able to compute globally optimal layouts for SRFLPs with up to 30 facilities. This paper further explores the application of SDP to this problem. First, we revisit the recently proposed quadratic formulation of this problem that underlies the SDP relaxation and provide an independent proof that the feasible set of the formulation is a precise representation of the set of all permutations on n objects. This fact follows from earlier work of Murata et al., but a proof in terms of the variables and structure of the SDP construction provides interesting insights into our approach. Second, we propose a new matrix-based formulation that yields a new SDP relaxation with fewer linear constraints but still yielding high-quality global lower bounds. Using this new relaxation, we are able to compute nearly optimal solutions for instances with up to 100 facilities.

Keywords:

• single-row facility layout
• space allocation
• combinatorial optimization
• semidefinite optimization
• global optimization

Acknowledgements

The authors thank Brian Borchers for his assistance in installing the CSDP and ATLAS software used to obtain the computational results. Parts of this research were completed while the first author was a Visiting Fellow at Princeton University. He thanks Robert J. Vanderbei and all the members of the ORFE department for their hospitality. The authors also thank two anonymous referees for their comments, which significantly improved this paper.

This research was partially supported by grants 312125 and 314668 from the Natural Sciences and Engineering Research Council of Canada, an Ontario Graduate Scholarship in Science and Technology, and by a TD Bank Graduate Scholarship in the Environment.

Additional information

Notes on contributors

Ginger Yen

Present address: IMS Management Consulting, 6755 Mississauga Road, Suite 200, Mississauga, ON, Canada L5N 7Y2.