A branch-and-bound algorithm for the continuous facility layout problem

Finding optimal facility layouts is a classic problem in process system engineering as well as operations research. As initial models were unsuitable for instances of unequal facility sizes or unknown potential positions, continuous facility layout (CFL) models were introduced to address these limitations by modeling facilities as geometric entities and searching for an optimal two-dimensional packing. However, solving these new models becomes dramatically harder: finding optimal layouts for these models is beyond reach of current optimization techniques, except for tiny instances. In this paper, we present several important theoretical results. We prove that it suffices to enumerate finitely many candidate solutions to secure an optimal solution, despite the fact that CFL admits infinitely many feasible layouts. We then develop a specialized branch-and-bound algorithm to further boost search efficiency by exploiting problem structure to prune large portions of the solution space. Comprehensive computational studies show that this new algorithm substantially outperforms three existing approaches. We also discuss extensions of this algorithm to more general layout instances.