Facility layout problems: solution approaches and practical difficult...

Facility layout problems are an extremely challenging class of optimization problems with many practical applications, such as designing a cost-efficient factory. In this talk, we will mainly focus on the so-called single row facility layout problem (SRFLP). It asks for an arrangement of n one-dimensional facilities of given lengths on a straight line, while minimizing a weighted sum of distances between all facility pairs. We will show how the SRFLP can be tackled by mathematical programming and why it is so hard to solve instances of modest size within reasonable time. Besides the most successful solution approach based on linear programming, we also present the state-of-the-art semidefinite relaxations and how they can be solved approximately for large-scale instances. Finally, we briefly address the related double row facility layout problem (DRFLP), and why it imposes even more challenges.