Shapes and recession cones in mixed-integer convex representability
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Science and Business Media LLC
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/153535 |
| _version_ | 1824458259243728896 |
|---|---|
| author | Zadik, Ilias Lubin, Miles Vielma, Juan Pablo |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Zadik, Ilias Lubin, Miles Vielma, Juan Pablo |
| author_sort | Zadik, Ilias |
| collection | MIT |
| description | Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves. |
| first_indexed | 2024-09-23T13:51:16Z |
| format | Article |
| id | mit-1721.1/153535 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:23:03Z |
| publishDate | 2024 |
| publisher | Springer Science and Business Media LLC |
| record_format | dspace |
| spelling | mit-1721.1/1535352025-01-03T04:58:34Z Shapes and recession cones in mixed-integer convex representability Zadik, Ilias Lubin, Miles Vielma, Juan Pablo Massachusetts Institute of Technology. Department of Mathematics General Mathematics Software Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves. 2024-02-16T14:29:33Z 2024-02-16T14:29:33Z 2023-03-30 2024-02-16T04:25:43Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 https://hdl.handle.net/1721.1/153535 Zadik, I., Lubin, M. & Vielma, J.P. Shapes and recession cones in mixed-integer convex representability. Math. Program. 204, 739–752 (2024). en 10.1007/s10107-023-01946-4 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Science and Business Media LLC Springer Berlin Heidelberg |
| spellingShingle | General Mathematics Software Zadik, Ilias Lubin, Miles Vielma, Juan Pablo Shapes and recession cones in mixed-integer convex representability |
| title | Shapes and recession cones in mixed-integer convex representability |
| title_full | Shapes and recession cones in mixed-integer convex representability |
| title_fullStr | Shapes and recession cones in mixed-integer convex representability |
| title_full_unstemmed | Shapes and recession cones in mixed-integer convex representability |
| title_short | Shapes and recession cones in mixed-integer convex representability |
| title_sort | shapes and recession cones in mixed integer convex representability |
| topic | General Mathematics Software |
| url | https://hdl.handle.net/1721.1/153535 |
| work_keys_str_mv | AT zadikilias shapesandrecessionconesinmixedintegerconvexrepresentability AT lubinmiles shapesandrecessionconesinmixedintegerconvexrepresentability AT vielmajuanpablo shapesandrecessionconesinmixedintegerconvexrepresentability |