Optimization Online


Strong mixed-integer formulations for the floor layout problem

Joey Huchette(huchette***at***mit.edu)
Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Juan Pablo Vielma(jvielma***at***mit.edu)

Abstract: The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes a systematic approach to constructing MIP formulations and valid inequalities for the FLP that unifies and recovers all known formulations for it. In addition, the approach yields new formulations that can provide a significant computational advantage and can solve previously unsolved instances. While the construction approach focuses on the FLP, it also exemplifies generic formulation techniques that should prove useful for broader classes of problems.

Keywords: layout, integer programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Citation: Submitted for publication.

Download: [PDF]

Entry Submitted: 02/24/2016
Entry Accepted: 02/24/2016
Entry Last Modified: 02/24/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society