Optimization Online


Beating the SDP bound for the floor layout problem: A simple combinatorial idea

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

Abstract: For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the "combinatorial implosion" effect by solving portions of the original problem and aggregating this information to obtain a global dual bound. We apply this technique to the one-dimensional and two-dimensional floor layout problems and compare it with the bounds generated by both state-of-the-art MIP solvers and by SDP relaxations. Specifically, we prove that the bounds obtained through the proposed technique are at least as good as those obtained through SDP relaxations, and present computational results that these bounds can be significantly stronger and easier to compute than these alternative strategies, particularly for very difficult problem instances.

Keywords: layout, integer programming

Category 1: Integer 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