Strong mixed-integer formulations for the floor layout problem
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 remai...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
University of Toronto Press Inc
2019
|
| Online Access: | http://hdl.handle.net/1721.1/121061 https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1826206477213237248 |
|---|---|
| author | Dey, Santanu S. Huchette, Joey Vielma, Juan Pablo |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Dey, Santanu S. Huchette, Joey Vielma, Juan Pablo |
| author_sort | Dey, Santanu S. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:32:38Z |
| format | Article |
| id | mit-1721.1/121061 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:32:38Z |
| publishDate | 2019 |
| publisher | University of Toronto Press Inc |
| record_format | dspace |
| spelling | mit-1721.1/1210612023-03-01T02:14:04Z Strong mixed-integer formulations for the floor layout problem Dey, Santanu S. Huchette, Joey Vielma, Juan Pablo Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Huchette, Joey Vielma Centeno, Juan Pablo 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. United States. National Science Foundation. Graduate Research Fellowship Program (Grant 1122374) United States. National Science Foundation. Graduate Research Fellowship Program (Grant CMMI-1351619) 2019-03-22T18:03:41Z 2019-03-22T18:03:41Z 2017-07 2017-04 2019-03-05T17:09:30Z Article http://purl.org/eprint/type/JournalArticle 0315-5986 1916-0615 http://hdl.handle.net/1721.1/121061 Huchette, Joey et al. “Strong Mixed-Integer Formulations for the Floor Layout Problem.” INFOR: Information Systems and Operational Research 56, 4 (July 2017): 392–433. doi:10.1080/03155986.2017.1346916. © 2017 The Author(s) https://orcid.org/0000-0003-4335-7248 http://dx.doi.org/10.1080/03155986.2017.1346916 INFOR Information Systems and Operational Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf University of Toronto Press Inc arXiv |
| spellingShingle | Dey, Santanu S. Huchette, Joey Vielma, Juan Pablo Strong mixed-integer formulations for the floor layout problem |
| title | Strong mixed-integer formulations for the floor layout problem |
| title_full | Strong mixed-integer formulations for the floor layout problem |
| title_fullStr | Strong mixed-integer formulations for the floor layout problem |
| title_full_unstemmed | Strong mixed-integer formulations for the floor layout problem |
| title_short | Strong mixed-integer formulations for the floor layout problem |
| title_sort | strong mixed integer formulations for the floor layout problem |
| url | http://hdl.handle.net/1721.1/121061 https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT deysantanus strongmixedintegerformulationsforthefloorlayoutproblem AT huchettejoey strongmixedintegerformulationsforthefloorlayoutproblem AT vielmajuanpablo strongmixedintegerformulationsforthefloorlayoutproblem |