Timezone: »

 
Poster
Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
Maria-Florina Balcan · Siddharth Prasad · Tuomas Sandholm · Ellen Vitercik

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #741
in Poster Session 5 »

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 discrete optimization problems and thus have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.

Keywords: data-driven algorithm design · Sample Complexity · Gomory mixed integer cuts · automated algorithm configuration · branch-and-bound · generalization guarantees · branch-and-cut · integer programming · tree search · cutting planes
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Maria-Florina Balcan (Carnegie Mellon University)
Siddharth Prasad (Computer Science Department, Carnegie Mellon University)
Tuomas Sandholm (CMU, Strategic Machine, Strategy Robot, Optimized Markets)
Ellen Vitercik (University of California, Berkeley)

More from the Same Authors