Title: Disjunctive Cuts through the V-Polyhedral Lens
| Speaker: | Aleksandr Kazachkov |
| Affiliation: | Polytechnique Montréal |
| Room: | MC 5501 |
Abstract:
Cutting planes, or cuts, are a critical component of modern integer programming solvers, but existing cuts implemented in solvers are relatively simple compared to those in the literature. We discuss the primary reasons for this disparity, as well as our recently-proposed V-polyhedral framework for mitigating some of these difficulties encountered by prior "stronger" cuts. We build a compact linear program to generate strong disjunctive cuts without resorting to a higher-dimensional formulation, such as the one used in the standard alternative, lift-and-project. Though computationally more efficient, V-polyhedral cuts cannot be directly strengthened via classical approaches, which use the values of the extra variables appearing in the lift-and-project formulation. We show how to compute these values from a solution to the linear program generating V-polyhedral disjunctive cuts, enabling future research on strengthening these cuts.
In addition to proving useful theoretical properties of the cuts, we perform computational testing of their performance through an implementation in the open source COIN-OR framework, tested with strong multiterm disjunctions built from the leaf nodes of a partial branch-and-bound tree. Our results indicate that V-polyhedral cuts significantly improve the integrality gap closed compared to reasonable baselines and that they can also decrease solving time when used with branch-and-bound within a commercial solver. The outcome shows that the V-polyhedral framework is a promising path forward to effectively using stronger cuts within solvers.