论文标题
分支和切割的结构分析以及Gomory混合整数切割的可学习性
Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
论文作者
论文摘要
在分支和结合算法中的切割平面（称为分支切割）的结合形成了现代整数编程求解器的骨干。这些求解器是解决离散优化问题的最重要方法，因此在机器学习，操作研究和许多其他领域中具有大量应用。有效地选择切割平面是整数编程理论和实践中的主要研究主题。我们对分支和切割的新结构分析进行了新的结构分析，该分析将算法的每个步骤都受到定义添加到输入整数程序的切割平面的参数的变化的影响。我们的主要应用程序是为了确定使用机器学习来确定在分支切割过程中使用哪种切割平面的样本复杂性保证。这些保证适用于无限的切割飞机家族，例如Gomory混合整数切割家族，这些家族负责整数编程求解器的主要突破性加速。我们在分析中利用分支和切割的几何和组合结构，这为最近的分支和切割的概括理论提供了关键的缺失。
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.
