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

Wei Xie, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1016-1028
Number of pages13
JournalComputers and Chemical Engineering
Volume32
Issue number4-5
DOIs
StatePublished - Apr 5 2008

Keywords

  • Branch-and-bound
  • Facility layout
  • Minimum cost network flow
  • Permutation tree
  • Sequence-pair

ASJC Scopus subject areas

  • General Chemical Engineering
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'A branch-and-bound algorithm for the continuous facility layout problem'. Together they form a unique fingerprint.

Cite this