清华团队提出使用低维优化求解器求解高维、大规模优化问题的方法

编辑 | 紫菜

在 2023 年 7 月即将召开的机器学习领域知名国际会议 ICML2023 中，清华大学计算机系徐华老师团队以长文的形式发表了采用低维优化求解器求解高维/大规模优化问题的最新研究成果(论文标题「GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming」)。

这项研究针对工业界对于大规模整数规划问题的高效求解需求，提出了基于图卷积神经网络和梯度提升决策树的三阶段优化求解框架，探索了仅使用小规模、免费、开源的优化求解器求解只有商用优化求解器才能解决的大规模优化问题的道路，在电力系统、物流配送、路径规划等诸多应用领域中均具有潜在的应用价值。

研究背景

现实生活和工业领域中很多问题都可以抽象为一类工程优化问题，例如对于外卖员的调度问题是大规模优化领域中一类典型的高维整数规划问题。对于大规模整数规划问题求解方法的研究，在电力系统调度、物流配送规划、路径规划等诸多实际应用领域，具有重要广阔的应用前景和商业价值。

然而，由于免费开源的学术和商用求解器的能力限制，目前对于以大规模整数规划问题为代表的高维优化问题的求解，通常依赖于商用求解器，一方面具有较高的计算成本和代价，另一方面计算结果常常难以再进一步的优化。大规模优化求解器的研制也是我们在科学计算领域所面临又一「卡脖子」问题。

近年来，基于神经下潜的策略实现优化问题的求解为利用人工智能领域的最新成果实现对于大规模优化问题的求解开辟了一条崭新的实现路径。

为充分利用已有的学术、商用开源的优化求解器在低维优化问题的求解能力，同时提升其在大规模优化求解的能力，清华大学计算机系徐华老师团队，针对大规模整数规划问题这一典型的高维优化问题，提出了一种融合神经下潜、梯度决策树和大邻域搜索策略的大规模整数规划问题的求解方法，该方法可以有效利用当前免费、开源和低维的学术优化求解器(SCIP)和商用优化求解器(Gurobi免费版)实现对于大规模整数规划问题的高效求解。

实验表明，该框架可以仅使用原问题规模30%大小的求解器解决百万级别的整数规划问题，并且在相同的运行时间下能够得到比商用优化求解器Gurobi和学术优化求解器SCIP更好的结果。此外，在部份优化问题上，该框架还能够节约99%的运行时间以达到和SCIP相同的求解质量，进一步验证了该方法在解决大规模整数规划问题时的有效性和高效性。

高效方法

针对大规模整数规划问题这一典型的高维优化问题，清华研究团队提出了一种融合神经下潜、梯度决策树和大邻域搜索策略的大规模整数规划问题的求解方法。该方法在求解大规模整数规划优化问题时，如图1所示，可以简单地分为三个阶段：多任务图神经网络编码阶段、梯度提升决策树预测阶段和邻域优化阶段。

在多任务图神经网络编码阶段，首先将整数规划问题表示为二分图的形式并使用图划分算法（FENNEL）将二分图进行划分，接着使用具有半卷积结构的多任务图神经网络来学习决策变量的神经编码表示，其中损失函数将同时考虑该问题最优解值和图划分结果的度量函数。

在梯度提升决策树预测阶段，使用梯度提升决策树通过神经编码结果来预测整数规划问题中对应的决策变量的最优解值，并同时生成邻域划分的指导信息。在邻域优化阶段，大部分决策变量被固定为梯度提升决策树预测结果的舍入值，而剩余的决策变量则使用固定半径搜索来找到初始解值。

在邻域划分结果的指导下，使用固定搜索半径的邻域搜索和邻域间解的小规模交叉来迭代改进当前解，直至达到预设的终止时间或终止条件。实验结果表明，研究团队所提出的方法可以有效地解决大规模整数规划问题，具有很高的实用价值。

图1 融合神经下潜、梯度决策树和大邻域搜索策略的大规模整数规划问题的求解方法框图

实验结果

为了验证融合神经下潜、梯度决策树和大邻域搜索策略的大规模整数规划问题求解方法的有效性，研究团队在四个标准优化问题（组合拍卖（CA）、最大独立集（MIS）、最小点覆盖（MVC）和集合覆盖（SC））以及真实互联网领域的实际问题（IP）上进行了测试，学术求解器SCIP 和商用求解器 Gurobi 作为对比的大规模基线求解算法，并使用它们的规模受限版本作为优化阶段的小规模求解器，进行了全面的对比实验，以展示所提出优化求解方法的优势。

重要实验结果如下所示。

实验一：相同运算时间下，与SCIP、Gurobi的计算结果对比

实验二：相同优化目标下，与SCIP、Gurobi的计算时间对比

实验三：相同计算时间下，与SCIP、Gurobi的小规模问题求解结果对比

实验四：相同优化结果下，与SCIP、Gurobi在小规模问题上求解时间对比

创新总结

针对大规模整数规划为代表的一类高维优化问题，清华研究团队所提出的基于图卷积神经网络和梯度提升决策树的优化求解框架是一种高效且具有突破性的求解方法。与经典优化方法相比，在实际问题求解上呈现了如下几个方面的核心创新：

在AI for Science领域研究了一种基于神经下潜策略的大规模优化问题的有效求解方法；

实现了使用当前免费、开源和小规模优化求解器对于大规模优化问题（整数规划问题为例）的求解，无论在求解的精度和求解效率上均优于目前的商用优化求解器和学术优化求解器。

为混合整数规划问题、组合优化等其它类型的大规模优化问题求解指明了一条崭新的、高效的、可行的、低成本的优化求解思路。

未来在超大规模、多目标、动态、非线性约束等为特征的优化难题上具有高效求解的潜力和应用价值。

文章链接：https://openreview.net/forum?id=tX7ajV69wt