Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.
翻译:切开的平面是最新混合整数编程解析器的关键组成部分,选择哪一组剪切对于求解器性能至关重要。我们提出新的远程措施,通过量化其分离宽松的可行套件相关部分的程度来限定剪切值。为此,我们使用放松聚点或其最佳面部的分析中心,以及线性编程放松的替代最佳解决办法。我们评估选择距离测量器对根节性能和整个分支和直径树的影响,比较我们与文献中流行的措施。最后,通过多输出回归,我们利用分离过程之前随时可用的静态特征预测每项措施的相对性能。我们的结果表明,以中心为基础的分析方法有助于大大减少探索搜索空间所需的分支和约束节点的数量,我们的多倒退方法可以进一步改进任何单个方法。