Cutting plane methods play a significant role in modern solvers for tackling
mixed-integer programming (MIP) problems. Proper selection of cuts would remove
infeasible solutions in the early stage, thus largely reducing the
computational burden without hurting the solution accuracy. However, the major
cut selection approaches heavily rely on heuristics, which strongly depend on
the specific problem at hand and thus limit their generalization capability. In
this paper, we propose a data-driven and generalizable cut selection approach,
named Cut Ranking, in the settings of multiple instance learning. To measure
the quality of the candidate cuts, a scoring function, which takes the
instance-specific cut features as inputs, is trained and applied in cut ranking
and selection. In order to evaluate our method, we conduct extensive
experiments on both synthetic datasets and real-world datasets. Compared with
commonly used heuristics for cut selection, the learning-based policy has shown
to be more effective, and is capable of generalizing over multiple problems
with different properties. Cut Ranking has been deployed in an industrial
solver for large-scale MIPs. In the online A/B testing of the product planning
problems with more than $10^7$ variables and constraints daily, Cut Ranking has
achieved the average speedup ratio of 12.42% over the production solver without
any accuracy loss of solution.

本文提出了一种数据驱动的、可推广的割平面方法 Cut Ranking，用于选择多实例学习中的切割。通过训练一个由特征决定的评分函数，该方法被证明比传统的启发式算法更为有效，可适用于具有不同特性的多种问题，且在实验和在线 A / B 测试中效果显著。