Cutting planes (cuts) are important for solving mixed-integer linear programs
(MILPs), which formulate a wide range of important real-world applications. Cut
selection -- which aims to select a proper subset of the candidate cuts to
improve the efficiency of solving MILPs -- heavily depends on (P1) which cuts
should be preferred, and (P2) how many cuts should be selected. Although many
modern MILP solvers tackle (P1)-(P2) by manually designed heuristics, machine
learning offers a promising approach to learn more effective heuristics from
MILPs collected from specific applications. However, many existing
learning-based methods focus on learning which cuts should be preferred,
neglecting the importance of learning the number of cuts that should be
selected. Moreover, we observe from extensive empirical results that (P3) what
order of selected cuts should be preferred has a significant impact on the
efficiency of solving MILPs as well. To address this challenge, we propose a
novel hierarchical sequence model (HEM) to learn cut selection policies via
reinforcement learning. Specifically, HEM consists of a two-level model: (1) a
higher-level model to learn the number of cuts that should be selected, (2) and
a lower-level model -- that formulates the cut selection task as a sequence to
sequence learning problem -- to learn policies selecting an ordered subset with
the size determined by the higher-level model. To the best of our knowledge,
HEM is the first method that can tackle (P1)-(P3) in cut selection
simultaneously from a data-driven perspective. Experiments show that HEM
significantly improves the efficiency of solving MILPs compared to
human-designed and learning-based baselines on both synthetic and large-scale
real-world MILPs, including MIPLIB 2017. Moreover, experiments demonstrate that
HEM well generalizes to MILPs that are significantly larger than those seen
during training.

通过强化学习，提出了一种新的层次序列模型（HEM），可以同时解决切割选择中的三个主要问题：（P1）哪些切割应该优先选择，（P2）应选择多少切割和（P3）优选选择的切割顺序对于求解混合整数线性规划问题的效率有显著影响。

通过层次序列模型学习混合整数线性规划的切割选择

Learning Cut Selection for Mixed-Integer Linear Programming via  Hierarchical Sequence Model

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 测试中效果显著。

学习选择剪枝以提高混合整数规划效率

Learning to Select Cuts for Efficient Mixed-Integer Programming

While many classes of cutting-planes are at the disposal of integer
programming solvers, our scientific understanding is far from complete with
regards to cutting-plane selection, i.e., the task of selecting a portfolio of
cutting-planes to be added to the LP relaxation at a given node of the
branch-and-bound tree. In this paper we review the different classes of
cutting-planes available, known theoretical results about their relative
strength, important issues pertaining to cut selection, and discuss some
possible new directions to be pursued in order to accomplish cutting-plane
selection in a more principled manner. Finally, we review some lines of work
that we undertook to provide a preliminary theoretical underpinning for some of
the issues related to cut selection.

对比不同种类的切割平面以及它们间的相对强度，讨论在分支定界树中选取一个投资组合的切割平面的问题，提出一些新的方法。在研究中，试图为切割平面选择设计出一种更为系统的方法。同时我们为与切割平面选择有关的一些问题提供了初步的理论基础。