Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
We study the generalization of split, k-branch split, and intersection cuts from mixed integer linear programming to the realm of mixed integer nonlinear programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geom...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103100 https://orcid.org/0000-0003-4335-7248 |
| _version_ | 1826189546572742656 |
|---|---|
| author | Modaresi, Sina Kılınç, Mustafa R. Vielma Centeno, Juan Pablo |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Modaresi, Sina Kılınç, Mustafa R. Vielma Centeno, Juan Pablo |
| author_sort | Modaresi, Sina |
| collection | MIT |
| description | We study the generalization of split, k-branch split, and intersection cuts from mixed integer linear programming to the realm of mixed integer nonlinear programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. In particular, we give simple formulas for split cuts for essentially all convex sets described by a single conic quadratic inequality. We also give simple formulas for k-branch split cuts and some general intersection cuts for a wide variety of convex quadratic sets. |
| first_indexed | 2024-09-23T08:16:35Z |
| format | Article |
| id | mit-1721.1/103100 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:16:35Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1031002022-09-30T08:48:11Z Intersection cuts for nonlinear integer programming: convexification techniques for structured sets Modaresi, Sina Kılınç, Mustafa R. Vielma Centeno, Juan Pablo Sloan School of Management Vielma Centeno, Juan Pablo We study the generalization of split, k-branch split, and intersection cuts from mixed integer linear programming to the realm of mixed integer nonlinear programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. In particular, we give simple formulas for split cuts for essentially all convex sets described by a single conic quadratic inequality. We also give simple formulas for k-branch split cuts and some general intersection cuts for a wide variety of convex quadratic sets. United States. Office of Naval Research (Grant N000141110724) National Science Foundation (U.S.) (Grant CMMI-1030662) 2016-06-14T14:55:27Z 2016-06-14T14:55:27Z 2015-02 2013-09 2016-05-23T12:11:23Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/103100 Modaresi, Sina, Mustafa R. Kılınç, and Juan Pablo Vielma. “Intersection Cuts for Nonlinear Integer Programming: Convexification Techniques for Structured Sets.” Math. Program. 155, no. 1–2 (February 17, 2015): 575–611. https://orcid.org/0000-0003-4335-7248 en http://dx.doi.org/10.1007/s10107-015-0866-5 Mathematical Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Modaresi, Sina Kılınç, Mustafa R. Vielma Centeno, Juan Pablo Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title | Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title_full | Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title_fullStr | Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title_full_unstemmed | Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title_short | Intersection cuts for nonlinear integer programming: convexification techniques for structured sets |
| title_sort | intersection cuts for nonlinear integer programming convexification techniques for structured sets |
| url | http://hdl.handle.net/1721.1/103100 https://orcid.org/0000-0003-4335-7248 |
| work_keys_str_mv | AT modaresisina intersectioncutsfornonlinearintegerprogrammingconvexificationtechniquesforstructuredsets AT kılıncmustafar intersectioncutsfornonlinearintegerprogrammingconvexificationtechniquesforstructuredsets AT vielmacentenojuanpablo intersectioncutsfornonlinearintegerprogrammingconvexificationtechniquesforstructuredsets |