An Exact Approach to the One-Dimensional Facility Layout Problem

The one-dimensional facility layout problem is concerned with arranging n departments of given lengths on a line, while minimizing the weighted sum of the distances between all pairs of departments. The problem is NP-hard because it is a generalization of the minimum linear arrangement problem. In this paper, a 0-1 quadratic programming model consisting of only O( n 2 ) 0-1 variables is proposed for the problem. Subsequently, this model is cast as an equivalent mixed-integer program and then reduced by preprocessing. Next, additional redundant constraints are introduced and linearized in a higher space to achieve an equivalent mixed 0-1 linear program, whose continuous relaxation provides an approximation of the convex hull of solutions to the quadratic program. It is shown that the resulting mixed 0-1 linear program is more efficient than previously published mixed-integer formulations. In the computational results, several problem instances taken from the literature were efficiently solved to optimality. Moreover, it is now possible to efficiently solve problems of a larger size.