Embedding Formulations and Complexity for Unions of Polyhedra
It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2019
|
| Online Access: | http://hdl.handle.net/1721.1/121064 https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1826201161483419648 |
|---|---|
| author | Vielma Centeno, Juan Pablo |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Vielma Centeno, Juan Pablo |
| author_sort | Vielma Centeno, Juan Pablo |
| collection | MIT |
| description | It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically,
they yield the smallest possible ideal formulation (i.e. one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal
formulations for SOS2 constraints and certain piecewise linear functions of two variables. We also show that the resulting formulations can provide a significant computational advantage over all known formulations
for piecewise linear functions. |
| first_indexed | 2024-09-23T11:47:11Z |
| format | Article |
| id | mit-1721.1/121064 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:47:11Z |
| publishDate | 2019 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1210642022-10-01T06:01:50Z Embedding Formulations and Complexity for Unions of Polyhedra Vielma Centeno, Juan Pablo Sloan School of Management Vielma Centeno, Juan Pablo It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically, they yield the smallest possible ideal formulation (i.e. one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal formulations for SOS2 constraints and certain piecewise linear functions of two variables. We also show that the resulting formulations can provide a significant computational advantage over all known formulations for piecewise linear functions. United States. National Science Foundation. (Grant CMMI-13516) 2019-03-22T18:27:51Z 2019-03-22T18:27:51Z 2017-11 2017-04 2019-03-05T16:57:10Z Article http://purl.org/eprint/type/JournalArticle 0025-1909 1526-5501 http://hdl.handle.net/1721.1/121064 Vielma, Juan Pablo. “Embedding Formulations and Complexity for Unions of Polyhedra.” Management Science 64, 10 (October 2018): 4721–4734. doi:10.1287/mnsc.2017.2856. © 2017 The Author https://orcid.org/0000-0003-4335-7248 http://dx.doi.org/10.1287/MNSC.2017.2856 Management Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Vielma Centeno, Juan Pablo Embedding Formulations and Complexity for Unions of Polyhedra |
| title | Embedding Formulations and Complexity for Unions of Polyhedra |
| title_full | Embedding Formulations and Complexity for Unions of Polyhedra |
| title_fullStr | Embedding Formulations and Complexity for Unions of Polyhedra |
| title_full_unstemmed | Embedding Formulations and Complexity for Unions of Polyhedra |
| title_short | Embedding Formulations and Complexity for Unions of Polyhedra |
| title_sort | embedding formulations and complexity for unions of polyhedra |
| url | http://hdl.handle.net/1721.1/121064 https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT vielmacentenojuanpablo embeddingformulationsandcomplexityforunionsofpolyhedra |