Enhanced Model Formulations for Optimal Facility Layout

This paper presents an improved mixed-integer programming (MIP) model and effective solution strategies for the facility layout problem and is motivated by the work of Meller et al. (1999). This class of problems seeks to determine a least-cost layout of departments having various size and area requirements within a rectangular building, and it is challenging even for small instances. The difficulty arises from the disjunctive constraints that prevent departmental overlaps and the nonlinear area constraints for each department, which existing models have failed to approximate with adequate accuracy. We develop several modeling and algorithmic enhancements that are demonstrated to produce more accurate solutions while also decreasing the solution effort required. We begin by deriving a novel polyhedral outer approximation scheme that can provide as accurate a representation of the area requirements as desired. We also design alternative methods for reducing problem symmetry, evaluate the performance of several classes of valid inequalities, explore the construction of partial convex hull representations for the disjunctive constraints, and investigate judicious branching variable selection priority schemes. The results indicate a substantial increase in the accuracy of the layout produced, while at the same time providing a dramatic reduction in computational effort. In particular, three previously unsolved test problems from the literature for which Meller et al.'s algorithm terminated prematurely after 24 cpu hours of computation (on a SUN Ultra 2 workstation with 390 MB RAM) with respective optimality gaps of 10.14%, 26.45%, and 40%, have been solved to exact optimality with reasonable effort using our proposed approach.