MIP Relaxations in Factorable Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916287974735872 |
|---|---|
| author | He, Taotao Tawarmalani, Mohit |
| author_facet | He, Taotao Tawarmalani, Mohit |
| contents | In this paper, we develop new discrete relaxations for nonlinear expressions in factorable programming. We utilize specialized convexification results as well as composite relaxations to develop mixed-integer programming (MIP) relaxations. Our relaxations rely on ideal formulations of convex hulls of outer-functions over a combinatorial structure that captures local inner-function structure. The resulting relaxations often require fewer variables and are tighter than currently prevalent ones. Finally, we provide computational evidence to demonstrate that our relaxations close approximately 60-70% of the gap relative to McCormick relaxations and significantly improves the relaxations used in a state-of-the-art solver on various instances involving polynomial functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07168 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | MIP Relaxations in Factorable Programming He, Taotao Tawarmalani, Mohit Optimization and Control In this paper, we develop new discrete relaxations for nonlinear expressions in factorable programming. We utilize specialized convexification results as well as composite relaxations to develop mixed-integer programming (MIP) relaxations. Our relaxations rely on ideal formulations of convex hulls of outer-functions over a combinatorial structure that captures local inner-function structure. The resulting relaxations often require fewer variables and are tighter than currently prevalent ones. Finally, we provide computational evidence to demonstrate that our relaxations close approximately 60-70% of the gap relative to McCormick relaxations and significantly improves the relaxations used in a state-of-the-art solver on various instances involving polynomial functions. |
| title | MIP Relaxations in Factorable Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2310.07168 |