Learning Cut Generating Functions for Integer Programming

分支定界算法是在实践中解决大规模整数规划问题的首选方法。分支定界算法的关键组成部分是使用割平面，这是导出的约束条件，可减少寻找最优解的搜索空间。选择有效的割平面以产生小的分支定界树是分支定界算法中的一个关键挑战。最近的进展采用数据驱动方法从参数化族中选择最佳割平面，旨在减少给定整数规划实例分布的分支定界树大小（期望）。我们将这个想法扩展到选择最佳割生成函数（CGF），它是整数规划文献中用于生成各种割平面的工具，可推广到众所周知的Gomory混合整数（GMI）割平面。我们为从某些参数化族中选择有效CGF的样本复杂度提供严格的界限，这些族可证明对于任何指定的问题实例分布都表现良好。我们的实证结果表明，所选的CGF可以在某些分布下优于GMI割。此外，我们还探讨了使用神经网络进行依赖于实例的CGF选择的样本复杂度。

选择最佳切割生成函数（CGF）的样本复杂度

通过数据驱动的方法，从参数化的家族中选择最优的CGF，以降低整数规划问题的搜索空间，同时提供了严格的样本复杂度界限。

论文提出的方法在某些分布下可以优于GMI切割方法，同时还探索了使用神经网络进行实例相关的CGF选择的样本复杂度。实验结果表明，选择的CGF可以在某些分布下优于GMI切割。

最近的相关研究包括使用数据驱动方法选择最佳切割平面和使用神经网络进行整数规划问题求解的研究。