$\mathcal{V}$-Polyhedral Disjunctive Cuts
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913236578729984 |
|---|---|
| author | Balas, Egon Kazachkov, Aleksandr M. |
| author_facet | Balas, Egon Kazachkov, Aleksandr M. |
| contents | We introduce $\mathcal{V}$-polyhedral disjunctive cuts (VPCs) for generating valid inequalities from general disjunctions. Cuts are critical to integer programming solvers, but the benefit from many families is only realized when the cuts are applied recursively, causing numerical instability and "tailing off" of cut strength after several rounds. To mitigate these difficulties, the VPC framework offers a practical method for generating strong cuts without resorting to recursion. The framework starts with a disjunction whose terms partition the feasible region into smaller subproblems, then obtains a collection of points and rays from the disjunctive terms, from which we build a linear program whose feasible solutions correspond to valid disjunctive cuts. Though a naïve implementation would result in an exponentially-sized optimization problem, we show how to efficiently construct this linear program, such that it is much smaller than the one from the alternative higher-dimensional cut-generating linear program. This enables us to test strong multiterm disjunctions that arise from the leaf nodes of a partial branch-and-bound tree. In addition to proving useful theoretical properties of the cuts, we evaluate their performance computationally through an implementation in the open-source COIN-OR framework. In the results, VPCs from a strong disjunction significantly improve the gap closed compared to existing cuts in solvers, and they also decrease some instances' solving time when used with branch and bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_13619 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | $\mathcal{V}$-Polyhedral Disjunctive Cuts Balas, Egon Kazachkov, Aleksandr M. Optimization and Control 90C11 We introduce $\mathcal{V}$-polyhedral disjunctive cuts (VPCs) for generating valid inequalities from general disjunctions. Cuts are critical to integer programming solvers, but the benefit from many families is only realized when the cuts are applied recursively, causing numerical instability and "tailing off" of cut strength after several rounds. To mitigate these difficulties, the VPC framework offers a practical method for generating strong cuts without resorting to recursion. The framework starts with a disjunction whose terms partition the feasible region into smaller subproblems, then obtains a collection of points and rays from the disjunctive terms, from which we build a linear program whose feasible solutions correspond to valid disjunctive cuts. Though a naïve implementation would result in an exponentially-sized optimization problem, we show how to efficiently construct this linear program, such that it is much smaller than the one from the alternative higher-dimensional cut-generating linear program. This enables us to test strong multiterm disjunctions that arise from the leaf nodes of a partial branch-and-bound tree. In addition to proving useful theoretical properties of the cuts, we evaluate their performance computationally through an implementation in the open-source COIN-OR framework. In the results, VPCs from a strong disjunction significantly improve the gap closed compared to existing cuts in solvers, and they also decrease some instances' solving time when used with branch and bound. |
| title | $\mathcal{V}$-Polyhedral Disjunctive Cuts |
| topic | Optimization and Control 90C11 |
| url | https://arxiv.org/abs/2207.13619 |