提升分支策略：学习改进分支方法

《European Journal of Operational Research》：Lifted branching: Learning to improve branching strategies

　　•一种新的机器学习框架能够迭代改进现有的混合整数线性规划分支策略。•提升式分支方法能够生成更小的搜索树，从而保持较低的决策时间。•经过训练的模型性能可超越现有的先进标准方法和模仿方法。•当问题具有结构相似性时，该方法表现尤为出色。

引言
当今各行业每天都会面临复杂的组合问题。例如规划不同发电厂的电力生产（Carroll等人，2017年；Montero等人，2022年）、在通信网络中路由数据包（Abdullah等人，2018年；Callebaut等人，2023年）、为不同司机规划送货路线（Golden等人，2023年）。这些例子仅是应用中的一小部分，更多应用可见于Petropoulos等人（2024年）的研究。这类组合问题旨在在离散空间中找到最优解。高效解决这些问题至关重要，但由于它们属于NP难问题（Karp，2010年），因此通常很难求解。

这类组合问题往往可以转化为混合整数线性规划问题。分支定界法是最常用的求解混合整数线性规划问题的算法。该方法通过递归探索解空间，同时解决一些简化后的问题。在此过程中，会利用一些界限来修剪分支定界树，从而减少所需步骤数。作为一种精确算法，它还能在求解过程中找到可行解，并能评估其质量。

分支定界法的成功依赖于多种启发式方法，如节点选择或分支策略，这些方法会对分支定界树的最终规模及求解时间产生很大影响。节点选择策略决定了每一步要探索哪个解空间，而分支策略则决定了如何对空间进行划分。

为提高分支定界法的效率，近期研究（Alvarez等人，2017年；Gasse等人，2019年）利用了这样一个事实：日常需要解决的混合整数线性规划问题往往非常相似，仅在某些参数上存在差异。基于这一观察，研究者们在分支定界法的各个阶段采用了基于机器学习的方法。其中，Gasse等人（2019年）的一项成功应用就是利用机器学习模型来模仿某种分支策略，这种策略虽然能生成较小的分支定界树，但实际应用中耗时过长。其他研究，如Etheve等人（2020年）、Parsonson等人（2023年）以及Scavuzzo等人（2022年），则采用强化学习方法来探索可能适用于特定问题的新分支策略。

一方面，试图模仿现有策略无法发现新策略；另一方面，强化学习也难以产生比求解器默认策略更好的策略。本研究的主要目标是构建一个机器学习框架，该框架能够生成能够产生更小分支定界树且求解速度更快的分支策略，同时避免在部署时出现强大分支策略所带来的过高计算成本。为实现这一目标，我们提出了提升式分支法，这是一种新型框架，它通过利用模仿学习从改进后的策略版本中学习，从而迭代改进现有的分支策略。这种方法介于简单模仿现有策略和运用强化学习之间，因为通过迭代应用该方法，它能够发现新策略。

计算实验表明，该框架在结构化领域具有良好效果。在单元调度和带容量限制的设施选址问题上，与SCIP的默认可靠性伪分支法以及现有的先进模仿学习基准方法相比，经过训练的模型在处理困难实例时能实现更短的求解时间。不过，这些结果也凸显出标准图卷积神经网络在这一领域的表达能力局限性。具体而言，图卷积神经网络在精确复制提升式策略的节点级决策方面准确率较低。尽管预测精度有限，但这种架构仍能提取出一种通用策略，从而降低特定问题类别的整体求解时间。

本文其余部分的结构如下：第2节介绍混合整数线性规划、分支定界法以及图卷积神经网络处理的双分图表示方法的相关背景。第3节回顾相关研究，详细阐述近期用于分支策略的机器学习和模仿学习方法。第4节介绍提升式分支策略，包括其设计思路、作为马尔可夫决策过程的正式表述，以及用于减少计算时间的近似方法。第5节详细介绍所设计的提升式分支框架，包括数据集生成、模型应用以及迭代学习过程。第6节报告我们在四个基准问题上的大规模计算实验，分析模型精度及性能与现有先进基准方法的对比情况。最后，第7节对本文进行总结，并探讨未来的研究方向。

片段摘录
混合整数线性规划与分支定界法
混合整数线性规划是一种优化问题，其目标是在满足一组线性约束条件Ax≤b的同时，最小化线性函数c?x。此外，某些变量必须是整数，即xi∈Z?i∈I?N，其中N为所有变量索引的集合。该问题可表示为：MILP=argminx{c?x|Ax≤b,xi∈Z?i∈I,xj∈R+?j∈N?I}。求解混合整数线性规划最常用的方法是分支定界法（Land & Doig，2010年），该方法通过递归分割解空间来逐步求解。

相关研究
在文献中，利用机器学习改进混合整数线性规划求解并非新想法。过去十年中，有多篇论文将机器学习技术应用于分支定界法的各种子流程中。Chmiela等人（2021年）和Hendel（2022年）利用机器学习技术来规划用于寻找原始解的各种启发式方法。在节点选择方面，机器学习被用来学习一种策略，该策略用于选择通往最优解路径上的节点（He等人，2014年），或通往较好解路径上的节点（Yilmaz & Yorke-Smith）。

设计分支策略时的考量
在为分支定界法设计分支策略时，必须仔细权衡策略的效率与其时间效率——即策略生成较小分支定界树的能力与做出决策所需的时间。如果一种策略虽然能生成最小的分支定界树，但决策所需时间却超过用其他策略解决整个问题所需的时间，那这种策略也就毫无意义。RPB就是一个体现这种权衡的例子，它需要在使用强大分支策略与控制决策时间之间找到平衡。

提升式分支法
提升式分支法的计算强度源于需要完全遍历分支定界树以对候选变量进行评分。由于时间复杂度过高，这种方法并不适用于实际应用，但非常适合用于离线生成机器学习模型的训练数据。这些模型可以学会估算提升式分支法中使用的评分函数，从而使该策略得以实际应用。

实验
本节评估了所设计的提升式分支策略与现有基准方法的性能对比，这些基准方法包括强大分支策略、可靠性伪分支法，以及Gasse等人（2019年）提出的强大分支策略的机器学习版本。

结论
本文介绍了提升式分支法，这是一种通过模仿学习机制迭代改进混合整数线性规划中分支策略的新型框架。通过这种方法，我们实证证明了利用图卷积神经网络改进现有策略的潜力，比如可靠性分支策略以及强大分支策略的模仿学习策略。我们的迭代提升式方法使得可以利用离线计算资源来探索和改进分支策略。

作者贡献说明
Simon Renard：撰写原文初稿、验证、软件开发、方法设计、概念构思。Quentin Louveaux：方法设计、概念构思。Bernard Fortz：监督指导、方法设计、概念构思。

利益冲突声明
作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。

致谢
计算资源由比利时科学研究基金会在Grant No. 2.5020.11项目下的强烈计算设备联盟（CéCI）以及瓦隆大区提供支持。

Simon Renard | Quentin Louveaux | Bernard Fortz