This event is open to the public and registration is not required.
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 and then propose a new framework that mitigates some of the difficulties encountered by prior methods. For example, the benefit of existing cuts is only realized when they are applied recursively. This in turn leads to undesirable consequences, such as increased numerical instability and the “tailing off” effect.
We take a V-polyhedral perspective on generating valid inequalities from general disjunctions that provides a practical method for generating strong cuts without resorting to recursion. The framework involves collecting a properly selected set of points and rays from which we build a linear program whose feasible solutions correspond to valid disjunctive cuts. Counterintuitively, we show a way to construct this linear program such that it is much smaller than the existing alternative, enabling us to efficiently test strong multiterm disjunctions. We build these disjunctions from the leaf nodes of a partial branch-and-bound tree, which is a step towards a tighter integration of the cutting and branching components of an integer programming solver.
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. Our results indicate that the V-polyhedral cuts significantly improve the integrality gap closed compared to standard baselines and that they can also decrease solving time when used with branch-and-bound. The outcome is is a promising procedure for practice, which also motivates and facilitates important future research directions on better understanding the interaction between branch-and-bound and cuts.
Speaker Bio
Aleksandr M. Kazachkov is a postdoctoral researcher at Polytechnique Montréal under Andrea Lodi. He received his Ph.D. in the Algorithms, Combinatorics, and Optimization program at the Tepper School of Business at Carnegie Mellon University, under Egon Balas. He does research in both operations research and artificial intelligence, and in their intersection, with focuses in discrete optimization and computational social choice. His prior work includes research on cutting plane algorithms, fair division, and fair mechanism design.
The Operations Research (OR) seminar series brings together graduate students, faculty and researchers from the University of Toronto community to interact with prominent scholars in the field of OR. Seminars feature visiting scholars from around the world as well as professors and post-docs. Topics include all variants of OR theory and their applications. Questions? Contact Merve Bodur at bodur@mie.utoronto.ca.