Incremental and encoding formulations for Mixed Integer Programming
The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formu...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107938 https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1811086376988311552 |
|---|---|
| author | Yıldız, Sercan Vielma Centeno, Juan Pablo |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Yıldız, Sercan Vielma Centeno, Juan Pablo |
| author_sort | Yıldız, Sercan |
| collection | MIT |
| description | The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones. |
| first_indexed | 2024-09-23T13:25:02Z |
| format | Article |
| id | mit-1721.1/107938 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:25:02Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1079382022-09-28T14:02:38Z Incremental and encoding formulations for Mixed Integer Programming Yıldız, Sercan Vielma Centeno, Juan Pablo Sloan School of Management Vielma Centeno, Juan Pablo The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones. 2017-04-07T15:38:35Z 2017-04-07T15:38:35Z 2013-09 2013-08 Article http://purl.org/eprint/type/JournalArticle 0167-6377 http://hdl.handle.net/1721.1/107938 Yıldız, Sercan, and Juan Pablo Vielma. “Incremental and Encoding Formulations for Mixed Integer Programming.” Operations Research Letters 41, no. 6 (November 2013): 654–658. https://orcid.org/0000-0003-4335-7248 en_US http://dx.doi.org/10.1016/j.orl.2013.09.004 Operations Research Letters Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier MIT web domain |
| spellingShingle | Yıldız, Sercan Vielma Centeno, Juan Pablo Incremental and encoding formulations for Mixed Integer Programming |
| title | Incremental and encoding formulations for Mixed Integer Programming |
| title_full | Incremental and encoding formulations for Mixed Integer Programming |
| title_fullStr | Incremental and encoding formulations for Mixed Integer Programming |
| title_full_unstemmed | Incremental and encoding formulations for Mixed Integer Programming |
| title_short | Incremental and encoding formulations for Mixed Integer Programming |
| title_sort | incremental and encoding formulations for mixed integer programming |
| url | http://hdl.handle.net/1721.1/107938 https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT yıldızsercan incrementalandencodingformulationsformixedintegerprogramming AT vielmacentenojuanpablo incrementalandencodingformulationsformixedintegerprogramming |