A semidefinite optimization-based approach for global optimization of multi-row facility layout

Philipp Hungerländer, Miguel F. Anjos

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper is concerned with the Multi-Row Facility Layout Problem. Given a set of rectangular departments, a fixed number of rows, and weights for each pair of departments, the problem consists of finding an assignment of departments to rows and the positions of the departments in each row so that the total weighted sum of the center-to-center distances between all pairs of departments is minimized. We show how to extend our recent approach for the Space-Free Multi-Row Facility Layout Problem to general Multi-Row Facility Layout as well as some special cases thereof. To the best of our knowledge this is the first global optimization approach for multi-row layout that is applicable beyond the double-row case. A key aspect of our proposed approach is a model for multi-row layout that expresses the problem as a discrete optimization problem, and thus makes it possible to exploit the underlying combinatorial structure. In particular we can explicitly control the number and size of the spaces between departments. We construct a semidefinite relaxation of the discrete optimization formulation and present computational results showing that the proposed approach gives promising results for several variants of multi-row layout problems on a variety of benchmark instances.
Original languageEnglish
Pages (from-to)46-61
JournalEuropean Journal of Operational Research
Issue number1
Early online date6 Mar 2015
Publication statusPublished - 1 Aug 2015


Dive into the research topics of 'A semidefinite optimization-based approach for global optimization of multi-row facility layout'. Together they form a unique fingerprint.

Cite this