In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global optimality by branching only on the variables in the backdoor. Constructing datasets of pre-computed backdoors for widely used MIP benchmark sets or particular problem families can enable new questions around novel structural properties of a MIP, or explain why a problem that is hard in theory can be solved efficiently in practice. Existing algorithms for finding backdoors rely on sampling candidate variable subsets in various ways, an approach which has demonstrated the existence of backdoors for some instances from MIPLIB2003 and MIPLIB2010. However, these algorithms fall short of consistently succeeding at the task due to an imbalance between exploration and exploitation. We propose BaMCTS, a Monte Carlo Tree Search framework for finding backdoors to MIPs. Extensive algorithmic engineering, hybridization with traditional MIP concepts, and close integration with the CPLEX solver have enabled our method to outperform baselines on MIPLIB2017 instances, finding backdoors more frequently and more efficiently.
翻译:在混合整形线性编程(MIP)中,一个(强)后门是一个“小”的“小”子集,是一例的整数变量,其属性如下:在分支和约束程序中,这个实例只能通过对后门变量的分流解决,从而实现全球最佳性。为广泛使用的 MIP 基准集或特定问题家庭建立预先计算出的后门数据集,可以围绕MIP 的新结构属性提出新问题,或者解释为什么理论上困难的问题在实际中能够有效解决。 现有查找后门的算法以各种方式抽样候选变量子集,这一方法已经证明存在后门,从MIPLIB 2003 和 MIPLIB 2010 中有些实例。然而,由于勘探和开发之间的不平衡,这些算法没有在任务上始终如一地成功。我们提议,一个蒙特卡洛树搜索框架,以寻找MIP 的后门。广泛的算法工程,与传统的MIP 概念混合,以及与CPLEX 求解器的密切结合,使得我们的方法在MIPLIB 2017 实例上经常地超越基准。