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

切割平面在解决混合整数线性规划（MILP）中起着重要作用，这种规划形式适用于许多重要的现实应用。切割选择严重依赖于两个问题：（P1）优先选择哪些切割和（P2）选择多少切割。虽然现代MILP求解器通过人工设计的启发式方法解决（P1）-（P2），但机器学习具有学习更有效启发式方法的潜力。然而，许多现有的基于学习的方法只学习了优先选择哪些切割，忽视了学习选择多少切割的重要性。此外，我们观察到（P3）选择的切割顺序对MILP求解器的效率有显着影响。为了解决这些挑战，我们提出了一种新的分层序列/集合模型（HEM）来学习切割选择策略。具体而言，HEM是一个双层模型：（1）一个更高层次的模块，学习选择多少个切割，（2）一个较低层次的模块，将切割选择作为一个序列/集合到序列学习问题，学习选择一个有序的子集，其基数由更高层次的模块确定。据我们所知，HEM是第一个同时很好地解决了（P1）-（P3）的数据驱动方法。实验证明，HEM显着提高了求解11个具有挑战性的MILP基准问题（包括两个华为的实际问题）的效率。

论文旨在解决混合整数线性规划中切割平面的选择问题，包括如何选择切割平面、选择多少切割平面以及选择切割平面的顺序问题。

论文提出了一种层次序列/集合模型（HEM），该模型通过双层学习来解决切割平面的选择问题。高层模块学习选择多少个切割平面，低层模块将切割平面的选择建模为序列/集合到序列的学习问题，学习选择一个有序子集，其基数由高层模块确定。

论文是第一篇同时解决切割平面选择中的三个问题的数据驱动方法。实验表明，HEM显著提高了解决混合整数线性规划问题的效率，在11个具有挑战性的基准测试中都表现出色，包括两个华为的实际问题。

近期的相关研究包括使用深度学习来预测切割平面的选择以及使用强化学习来决定切割平面的数量。其中一些研究包括：Learning to Cut: A Data-driven Approach to Decision Making in Cutting Plane Generation和Reinforcement Learning for Integer Programming: Learning to Cut。