《Expert Systems with Applications》：Air-Branching: Learning to Branch via Adversarial Inverse Reinforcement Learning in Mixed-Integer Linear Programming
编辑推荐：
摘要翻译：
Air-Branching采用对抗逆强化学习（Adversarial Inverse Reinforcement Learning, AIRL）来训练分支策略。Air-Branching同时解决了大规模数据需求和稀疏奖励问题。Air-Branch
摘要翻译：
Air-Branching采用对抗逆强化学习（Adversarial Inverse Reinforcement Learning, AIRL）来训练分支策略。Air-Branching同时解决了大规模数据需求和稀疏奖励问题。Air-Branching采用预热训练（warm-up training）来处理长回合问题。Air-Branching的联合奖励（joint reward）使其能够超越专家级性能。实验表明，Air-Branching在性能上优于模仿学习（Imitation Learning, IL）和强化学习（Reinforcement Learning, RL）两种训练范式。
1. 引言
混合整数线性规划（Mixed-Integer Linear Programming, MILP）是一类NP难问题，广泛应用于各种现实场景，包括调度（Chen, 2010）、规划（Pochet & Wolsey, 2006）和运输（Barnhart & Laporte, 2006）。分支定界（Branch-and-Bound, B&B）算法被公认为求解MILP最常用的精确方法，其依赖两个关键决策过程：分支变量选择（Branching Variable Selection, BVS）和节点选择。针对这些任务的有效策略能够显著减小B&B树的规模，并最小化整体计算时间。在Gurobi（Gurobi Optimization, 2024）和SCIP（Gamrath et al., 2020a）等主流MILP求解器中，通常采用启发式规则（例如强分支）来指导和优化这些决策过程，但这些规则依赖于手工设计的准则，可能无法在不同问题结构间很好地泛化。
近年来，越来越多的研究（Gasse, Chételat, Ferroni, Charlin, Lodi, 2019; Gupta, Gasse, Khalil, Mudigonda, Lodi, Bengio, 2020）转向基于学习的BVS方法，利用神经网络自动捕获问题特定的模式。在重复性的工业场景中，这些方法相较于启发式规则具有显著优势，因为可以挖掘MILP实例间共享的底层结构来加速求解。具体而言，当前基于学习的方法主要遵循两种范式：模仿学习（Imitation Learning, IL），利用监督学习训练神经网络模仿专家分支决策，通过最小化动作预测误差来实现；强化学习（Reinforcement Learning, RL），通过奖励驱动的探索来优化分支策略——通常以求解器效率指标（如运行时间缩减或节点数最小化）作为引导——而不依赖显式的专家示范。
虽然两种范式都旨在超越启发式规则，但它们在数据效率、性能上限和训练稳定性方面表现出不同的权衡。首先，IL方法主要依赖行为克隆（Behavioral Cloning, BC），这仍是训练BVS策略的最先进方法。然而，BC存在几个关键局限性：（1）大数据需求。由于协变量偏移引起的复合误差（Ho & Ermon, 2016），行为克隆需要大规模专家数据集才能有效。对于大规模MILP，生成此类数据集在计算上是不可行的。（2）无法超越专家性能。BC本质上受限于专家示范的质量。虽然专家分支规则通常计算成本高昂但准确性高，但IL方法无法超越这些示范的性能。相比之下，RL方法具有不依赖专家示范的优势，并具有超越专家级性能的理论潜力。然而，RL方法在实践中尚未超越行为克隆，主要原因有两个：（1）长回合问题。RL方法通常从随机策略开始，导致探索节点数量大幅增加，每个回合计算时间过长（Scavuzzo et al., 2022）。此外，长回合引入梯度估计的高方差（Sun, Chen, Li, & Song, 2021），使训练收敛更加困难。（2）稀疏奖励问题。BVS策略训练中的奖励（例如对偶界改进、MILP求解奖励）本质上是延迟且稀疏的，加剧了信用分配难题（Minsky, 1961），显著阻碍RL训练的有效性。
IL与RL之间的二分法揭示了一个基本权衡：IL以高数据成本实现可靠但有界的性能，而RL提供无界潜力但训练效率低下。尽管近期方法有所进展，例如在IL中增强专家示范识别（Gupta et al., 2022）或在RL中针对B&B特征定制马尔可夫决策过程（Scavuzzo et al., 2022），但这些方法主要分别在每种范式内部解决局限性。解决这一权衡需要开发新的混合学习范式，将IL的数据效率与RL的探索潜力协同结合，从而在利用其互补优势的同时缓解各自的局限。
在本文中，研究人员的核心见解在于：在稀疏奖励和有限样本可用性的条件下，逆强化学习（Inverse Reinforcement Learning, IRL）可以推导出专家奖励函数，从而促进通过RL方法高效训练BVS策略。为此，研究人员引入了对抗逆强化学习（Adversarial Inverse Reinforcement Learning, AIRL）框架（Fu, Luo, & Levine, 2018），并进一步提出了一种新方法，称为Air-Branching。具体而言，Air-Branching采用两阶段训练方法，包括预热训练和主训练。在预热训练阶段，收集强分支（strong branching）和反强分支（anti-strong branching）的样本以预训练判别器。该过程有助于获得可靠的专家奖励，并有效解决长回合问题。随后，在主RL训练阶段，使用联合奖励函数——结合专家推导的奖励和原始奖励信号——来训练BVS策略，从而释放超越专家性能的潜力。据研究人员所知，这是首次将IRL应用于学习BVS策略。研究人员的贡献总结如下：
•研究人员引入IRL来训练BVS策略，从而从本质上减少对大量数据的需求，同时从RL的角度解决与MILP相关的稀疏奖励问题。
•提出预热训练阶段以解决长回合问题。引入强分支和反强分支样本，并利用其预训练专家奖励函数。此外，为该方法的合理性提供了理论证明。
•使用AIRL训练专家奖励函数，并将其与原始奖励集成以指导RL训练，从而具备超越强分支专家的潜力。
•在实验中，Air-Branching在相同数据量（仅1000个样本）下优于IL基线，超越了RL基线以及最先进的开源求解器SCIP。此外，在真实世界基准和某些标准基准案例中，Air-Branching超过了使用10,000个样本训练的IL方法。
本文的其余部分组织如下。第2节回顾了基于学习的MILP求解相关工作。第3节介绍必要的预备知识，包括MILP公式、分支定界算法、二分图表示、BVS的MDP公式和AIRL框架。第4节描述所提出的Air-Branching方法，包括预热训练阶段和具有联合奖励的主训练阶段。第5节介绍实验设置、标准和真实世界基准的结果以及消融研究。第6节讨论Air-Branching的假设、局限性、与现有基于学习的分支方法的比较以及实际适用性。最后，第7节总结全文并讨论未来方向。
（后续章节翻译略，按用户要求仅翻译摘要部分。以上为摘要及引言完整翻译。）
论文解读：Air-Branching：基于对抗逆强化学习的混合整数线性规划分支策略
1. 研究背景与问题
混合整数线性规划（Mixed-Integer Linear Programming, MILP）作为一类NP难问题，在调度、规划、运输等现实场景中具有广泛应用。分支定界（Branch-and-Bound, B&B）算法是求解MILP最常用的精确方法，其性能高度依赖于分支变量选择（Branching Variable Selection, BVS）和节点选择两个关键决策。传统求解器如SCIP和Gurobi通常采用强分支（strong branching）等启发式规则，虽然决策精度高，但计算开销大且难以在不同问题结构间泛化。近年来，基于学习的BVS方法逐渐兴起，主要分为模仿学习（Imitation Learning, IL）和强化学习（Reinforcement Learning, RL）两类范式。IL通过行为克隆（Behavioral Cloning, BC）模仿专家决策，具有训练稳定的优点，但面临大规模专家数据需求高、无法超越专家性能的瓶颈；RL不依赖专家示范，理论上具备超越专家的潜力，但存在长回合问题和稀疏奖励问题，导致训练效率低下、收敛困难。IL与RL之间的权衡构成了当前研究的核心矛盾：如何兼顾IL的数据效率与RL的探索潜力，同时缓解各自的局限性。针对这一问题，研究人员提出将逆强化学习（Inverse Reinforcement Learning, IRL）引入BVS策略训练，利用少量专家示范学习专家奖励函数，再通过RL优化策略，从而在稀疏奖励和有限样本条件下实现高效训练。
2. 研究方法概述
Air-Branching采用两阶段训练框架。第一阶段为预热训练（warm-up training），同时收集强分支样本和反强分支样本（anti-strong branching），用于预训练AIRL框架中的判别器，使其快速获得可靠的专家奖励函数。反强分支策略通过强分支分数的负向softmax定义，作为判别器的负类样本，其生成过程与强分支样本并行，不增加额外计算开销。第二阶段为主训练阶段，判别器继续按标准AIRL方式训练，BVS策略则采用联合奖励函数进行优化，该联合奖励由原始奖励（如对偶界改进）和专家奖励加权求和构成，权重系数为α。策略网络和判别器均采用图卷积神经网络（Graph Convolutional Neural Network, GCNN）实现，RL环境基于Ecole库构建并与SCIP求解器交互，策略优化使用近端策略优化（Proximal Policy Optimization, PPO）算法。训练和评估使用四个标准基准问题：组合拍卖（Combinatorial Auctions, CA）、集合覆盖（Set Covering, SC）、最大独立集（Maximum Independent Set, MIS）和容量设施选址（Capacitated Facility Location, CFL），并在真实世界基准Balanced Item Placement（BIP）上进行验证。
3. 主要研究结果
3.1 标准基准实验结果
在四个标准基准上，Air-Branching在测试实例和迁移实例上的求解时间和节点数均显著优于所有RL基线（Vanilla PPO、tMDP+DFS），验证了IRL在训练分支策略中的优势。在与IL基线使用相同样本量（1000个）的条件下，Air-Branching在CA、CFL和MIS基准上优于IL，仅在SC上略逊。值得注意的是，在CA和CFL的测试实例以及MIS的测试和迁移实例上，Air-Branching以仅1000个样本实现了比使用10,000个样本的IL-more更短的求解时间，展示了优异的样本效率。与同样旨在降低数据成本的SORREL方法相比，Air-Branching在四个基准中的三个上表现更好或相当。此外，SCIP虽然节点数较少，但由于早期强分支计算开销大，其总求解时间反而长于Air-Branching。
3.2 真实世界基准结果
在BIP基准上，Air-Branching在1分钟、2分钟、5分钟和10分钟四种时间限制下的原始-对偶积分（primal-dual integral）均显著优于IL、IL-more和SCIP。IL和IL-more表现接近且较差，表明增加数据量并不能提升IL效果，原因是强分支本身仅考虑局部对偶界改进，在复杂真实问题中作为专家存在局限性。Air-Branching通过联合奖励实现全局对偶界改进，表现出最快的原始界收敛速度和更紧的对偶界，验证了其在复杂现实MILP中的有效性。
3.3 消融研究
联合奖励消融：仅使用专家奖励的AIRL（w/ warm-up）在求解时间和节点数上均劣于Air-Branching，证明联合奖励设计是超越专家性能的关键。联合奖励系数α敏感性分析显示，在MIS基准上，所有加入专家奖励的设置均优于仅原始奖励的Vanilla PPO，且性能随α增大先升后降，呈倒U型，最优值为α=1.0。预热训练消融：Vanilla PPO训练曲线无法收敛，而Air-Branching（无预热）能够收敛，说明专家奖励缓解了稀疏奖励问题；Air-Branching的曲线在初始阶段快速下降并稳定在最低节点数，而无预热版本在初始阶段出现明显振荡，验证了预热机制对加速收敛和解决长回合问题的作用。
4. 讨论与结论
讨论部分指出，Air-Branching适用于训练与部署实例共享底层结构的重复性MILP应用，即同类泛化场景，其假设强分支反馈能够区分优劣分支候选。局限性包括：在SC基准上，标签可能保留了足够的局部信息供IL使用，但同时模糊到足以削弱AIRL的成对奖励学习；此外，判别器和策略优化引入了额外的实现复杂度和计算成本，减少强分支示范并不一定等比例减少总墙钟时间。与IL相比，Air-Branching用有限强分支反馈学习专家奖励而非直接模仿；与Tree MDP和SORREL相比，Air-Branching从有限的高质量强分支反馈中学习，具有互补性。应用启示表明，当同一类MILP需要重复求解、强分支既信息丰富又代价高昂、且收集大规模IL数据不切实际时，Air-Branching最具吸引力；反之，当强分支便宜、已有大规模高质量示范数据集或强分支信号高度模糊时，传统IL可能更经济。
研究结论部分翻译如下：
本文提出了Air-Branching，一种基于AIRL的分支策略，首次引入IRL训练范式。即使训练样本有限，它也能超越强分支专家，同时解决BVS策略RL训练中固有的稀疏奖励和长回合挑战。Air-Branching的训练包括两个阶段：预热训练和主训练。在预热阶段，使用强分支和反强分支的样本初始化AIRL判别器，使其能够推导出专家奖励函数。在主AIRL训练阶段，判别器按照标准AIRL框架进行训练，而BVS策略使用联合奖励函数进行训练，该联合奖励结合了专家奖励和原始奖励。在实验中，Air-Branching在相同数据量下优于IL、所有RL基线和SCIP求解器。此外，在真实世界基准和某些标准基准案例中，Air-Branching超过了使用更多样本训练的IL方法。这些结果证明了其解决上述挑战的能力。未来工作将聚焦于低样本量下的学习方法的推进，力求在有限样本下进一步提升BVS策略的性能。
综上所述，Air-Branching通过将逆强化学习引入分支策略训练，有效缓解了IL与RL之间的权衡矛盾，在有限样本条件下实现了超越专家性能的潜力，为基于学习的MILP求解提供了新的研究范式。该研究发表于《Expert Systems with Applications》。
