The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear placement of facilities with varying dimensions on a straight line. We construct a semidefinite programming (SDP) relaxation providing a lower bound on the optimal value of the ODSAP. To the best of our knowledge, this is the first non-trivial global lower bound for the ODSAP in the published literature. This SDP approach implicitly takes into account the natural symmetry of the problem and, unlike other algorithms in the literature, does not require the use of any explicit symmetry-breaking constraints. Furthermore, the structure of the SDP relaxation suggests a simple heuristic procedure which extracts a feasible solution to the ODSAP from the optimal matrix solution to the SDP relaxation. Computational results show that this heuristic yields a solution which is consistently within a few percentage points of the global optimal solution.
Citation
Discrete Optimization, Vol. 2(2), 113-122, 2005.