Mixed-Integer Convex Representability
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the m...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Springer-Verlag
2019
|
| Online Access: | http://hdl.handle.net/1721.1/121062 https://orcid.org/0000-0001-6781-9633 https://orcid.org/0000-0002-8286-881X https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1826204709824757760 |
|---|---|
| author | Lubin, Miles C Zadik, Ilias Vielma, Juan Pablo |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Lubin, Miles C Zadik, Ilias Vielma, Juan Pablo |
| author_sort | Lubin, Miles C |
| collection | MIT |
| description | We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets; the latter case has been completely characterized in the context of mixed-integer linear optimization. |
| first_indexed | 2024-09-23T12:59:48Z |
| format | Article |
| id | mit-1721.1/121062 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:59:48Z |
| publishDate | 2019 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1210622023-03-01T02:08:10Z Mixed-Integer Convex Representability Lubin, Miles C Zadik, Ilias Vielma, Juan Pablo Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Lubin, Miles C Zadik, Ilias Vielma Centeno, Juan Pablo We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets; the latter case has been completely characterized in the context of mixed-integer linear optimization. United States. National Science Foundation. (Grant CMMI-1351619) 2019-03-22T18:19:07Z 2019-03-22T18:19:07Z 2017-05 2017-03 2019-03-05T17:03:39Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 http://hdl.handle.net/1721.1/121062 Lubin, Miles et al. “Mixed-Integer Convex Representability.” International Conference on Integer Programming and Combinatorial Optimization (2017): 392–404. doi:10.1007/978-3-319-59250-3_32. © 2017 The Author(s) https://orcid.org/0000-0001-6781-9633 https://orcid.org/0000-0002-8286-881X https://orcid.org/0000-0003-4335-7248 http://dx.doi.org/10.1007/978-3-319-59250-3_32 International Conference on Integer Programming and Combinatorial Optimization Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Lubin, Miles C Zadik, Ilias Vielma, Juan Pablo Mixed-Integer Convex Representability |
| title | Mixed-Integer Convex Representability |
| title_full | Mixed-Integer Convex Representability |
| title_fullStr | Mixed-Integer Convex Representability |
| title_full_unstemmed | Mixed-Integer Convex Representability |
| title_short | Mixed-Integer Convex Representability |
| title_sort | mixed integer convex representability |
| url | http://hdl.handle.net/1721.1/121062 https://orcid.org/0000-0001-6781-9633 https://orcid.org/0000-0002-8286-881X https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT lubinmilesc mixedintegerconvexrepresentability AT zadikilias mixedintegerconvexrepresentability AT vielmajuanpablo mixedintegerconvexrepresentability |