On the integrality gap of convex mixed-integer programs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908971643699200 |
|---|---|
| author | Kocuk, Burak Ramirez, Diego Moran |
| author_facet | Kocuk, Burak Ramirez, Diego Moran |
| contents | We study the integrality gap of convex mixed-integer programs, that is, the difference between the optimal value of such a problem and the optimal value of its continuous relaxation. We study classes of convex sets whose associated optimization problem have finite integrality gap: Dirichlet convex sets, sets with full-dimensional recession cones and sets that can be approximated by polyhedral sets. In the latter two cases, we provide estimates for the value of the integrality gap. Finally, we study the possibility of estimating the integrality gap of nonlinear convex mixed-integer programs via rational polyhedral approximations of their feasible regions and argue that, in general, such an approach may yield arbitrarily worse bounds compared to integrality gap estimations specifically derived by studying the associated nonlinear set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00638 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the integrality gap of convex mixed-integer programs Kocuk, Burak Ramirez, Diego Moran Optimization and Control We study the integrality gap of convex mixed-integer programs, that is, the difference between the optimal value of such a problem and the optimal value of its continuous relaxation. We study classes of convex sets whose associated optimization problem have finite integrality gap: Dirichlet convex sets, sets with full-dimensional recession cones and sets that can be approximated by polyhedral sets. In the latter two cases, we provide estimates for the value of the integrality gap. Finally, we study the possibility of estimating the integrality gap of nonlinear convex mixed-integer programs via rational polyhedral approximations of their feasible regions and argue that, in general, such an approach may yield arbitrarily worse bounds compared to integrality gap estimations specifically derived by studying the associated nonlinear set. |
| title | On the integrality gap of convex mixed-integer programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.00638 |