Parametric Disjunctive Cuts for Sequences of Mixed Integer Linear Optimization Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912719609790464 |
|---|---|
| author | Kelley, Shannon Kazachkov, Aleksandr M. Ralphs, Ted |
| author_facet | Kelley, Shannon Kazachkov, Aleksandr M. Ralphs, Ted |
| contents | Many applications require solving sequences of related mixed-integer linear programs. We introduce a class of parametric disjunctive inequalities (PDIs), obtained by reusing the disjunctive proofs of optimality from prior solves to construct cuts valid for perturbed instances. We describe several methods of generating such cuts that navigate the tradeoff between computational expense and strength. We provide sufficient conditions under which PDIs support the disjunctive hull and a tightening step that guarantees support when needed. On perturbed instances from MIPLIB 2017, augmenting branch-and-cut with PDIs substantially improves performance, reducing total solve times on the majority of challenging cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15873 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parametric Disjunctive Cuts for Sequences of Mixed Integer Linear Optimization Problems Kelley, Shannon Kazachkov, Aleksandr M. Ralphs, Ted Optimization and Control Many applications require solving sequences of related mixed-integer linear programs. We introduce a class of parametric disjunctive inequalities (PDIs), obtained by reusing the disjunctive proofs of optimality from prior solves to construct cuts valid for perturbed instances. We describe several methods of generating such cuts that navigate the tradeoff between computational expense and strength. We provide sufficient conditions under which PDIs support the disjunctive hull and a tightening step that guarantees support when needed. On perturbed instances from MIPLIB 2017, augmenting branch-and-cut with PDIs substantially improves performance, reducing total solve times on the majority of challenging cases. |
| title | Parametric Disjunctive Cuts for Sequences of Mixed Integer Linear Optimization Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.15873 |