Theory Lunch Seminar
Speaker
SIDDHARTH PRASAD
Ph.D. Student
Computer Science Department
Carnegie Mellon University
When
-
Where
In Person and Virtual - ET
Description
The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving various discrete optimization problems. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming.
In this talk, I will discuss our recent generalization theory that provides provable guarantees for machine learning approaches to cutting plane selection. These guarantees are obtained via a structural analysis of branch-and-cut, in which we pin down conditions for different cutting planes to lead to identical executions of branch-and-cut. I will present such guarantees for two cutting plane families of great practical importance: Chvátal-Gomory cuts and Gomory mixed integer cuts. Finally, I will discuss guarantees for parameter tuning in a general model of tree search, which yields the first provable guarantees for simultaneously tuning the main aspects of branch-and-cut: node selection, branching, and cutting plane selection.
Joint work with Nina Balcan, Tuomas Sandholm, and Ellen Vitercik.
The Theory Lunch is sponsored in part by Smart Contract Research Forum
In Person and Zoom Participation. See announcement.