Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

Understand

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.