Cutting planes (cuts) play an important role in solving mixed-integer linear
programs (MILPs), which formulate many important real-world applications. Cut
selection heavily depends on (P1) which cuts to prefer and (P2) how many cuts
to select. Although modern MILP solvers tackle (P1)-(P2) by human-designed
heuristics, machine learning carries the potential to learn more effective
heuristics. However, many existing learning-based methods learn which cuts to
prefer, neglecting the importance of learning how many cuts to select.
Moreover, we observe that (P3) what order of selected cuts to prefer
significantly impacts the efficiency of MILP solvers as well. To address these
challenges, we propose a novel hierarchical sequence/set model (HEM) to learn
cut selection policies. Specifically, HEM is a bi-level model: (1) a
higher-level module that learns how many cuts to select, (2) and a lower-level
module -- that formulates the cut selection as a sequence/set to sequence
learning problem -- to learn policies selecting an ordered subset with the
cardinality determined by the higher-level module. To the best of our
knowledge, HEM is the first data-driven methodology that well tackles (P1)-(P3)
simultaneously. Experiments demonstrate that HEM significantly improves the
efficiency of solving MILPs on eleven challenging MILP benchmarks, including
two Huawei's real problems.

我们提出了一种新的层次序列 / 集合模型（HEM），可以同时解决切割选择的三个挑战：学习要选择哪些切割、学习选择多少切割、以及学习选择顺序。实验证明，HEM 显著提高了求解 MILP 问题的效率。

通过分层序列 / 集合模型学习剪裁以实现高效混合整数规划

Learning to Cut via Hierarchical Sequence/Set Model for Efficient  Mixed-Integer Programming

Cutting planes are crucial in solving mixed integer linear programs (MILP) as
they facilitate bound improvements on the optimal solution. Modern MILP solvers
rely on a variety of separators to generate a diverse set of cutting planes by
invoking the separators frequently during the solving process. This work
identifies that MILP solvers can be drastically accelerated by appropriately
selecting separators to activate. As the combinatorial separator selection
space imposes challenges for machine learning, we learn to separate by
proposing a novel data-driven strategy to restrict the selection space and a
learning-guided algorithm on the restricted space. Our method predicts
instance-aware separator configurations which can dynamically adapt during the
solve, effectively accelerating the open source MILP solver SCIP by improving
the relative solve time up to 72% and 37% on synthetic and real-world MILP
benchmarks. Our work complements recent work on learning to select cutting
planes and highlights the importance of separator management.

本研究通过机器学习，在混合整数线性规划问题中选择切平面，以加速求解过程并提高求解时间。

学习在分支定界算法中配置分隔器

Learning to Configure Separators in Branch-and-Cut

We formalize the problem of trading-off DNN training time and memory
requirements as the tensor rematerialization optimization problem, a
generalization of prior checkpointing strategies. We introduce Checkmate, a
system that solves for optimal rematerialization schedules in reasonable times
(under an hour) using off-the-shelf MILP solvers or near-optimal schedules with
an approximation algorithm, then uses these schedules to accelerate millions of
training iterations. Our method scales to complex, realistic architectures and
is hardware-aware through the use of accelerator-specific, profile-based cost
models. In addition to reducing training cost, Checkmate enables real-world
networks to be trained with up to 5.1x larger input sizes. Checkmate is an
open-source project, available at this https URL

本篇研究论文提出了 Checkmate，这是一种针对训练 DNN 进行时间和内存要求的权衡的系统，它可以在不到一小时的时间内解决最佳重构日程表，并使用这些日程表加速数百万次的训练迭代，可适用于复杂的网络结构。