CORL: Reinforcement Learning of MILP Policies Solved via Branch and Bound

📄 arXiv: 2512.11169v1 📥 PDF

作者: Akhil S Anand, Elias Aarekol, Martin Mziray Dalseg, Magnus Stalhane, Sebastien Gros

分类: cs.AI, cs.LG, eess.SY, math.OC

发布日期: 2025-12-11

💡 一句话要点

提出CORL框架，通过强化学习端到端优化分支定界求解的MILP策略

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 混合整数线性规划 分支定界 组合优化 序列决策

📋 核心要点

  1. 现有方法难以构建精确的MILP模型来应对现实世界的随机性，导致决策质量下降。
  2. CORL框架将MILP求解过程视为可微随机策略，利用强化学习直接优化MILP方案。
  3. 通过实验验证，CORL方法在组合序列决策问题中展现了有效性。

📝 摘要（中文）

组合序列决策问题通常被建模为混合整数线性规划（MILP），并通过分支定界（B&B）算法求解。由于难以构建能够准确表示随机现实世界问题的MILP模型，导致实际应用中性能欠佳。最近，机器学习方法被应用于构建MILP模型，侧重于决策质量而非模型对现实世界的准确建模。然而，这些方法通常依赖于监督学习，假设可以获得真正的最优决策，并使用替代方法来估计MILP梯度。本文提出了一个概念验证的CORL框架，该框架使用强化学习（RL）在真实世界数据上端到端地微调MILP方案，以最大化其运营性能。通过将B&B求解的MILP转化为与RL兼容的可微随机策略来实现这一点。我们在一个简单的说明性组合序列决策示例中验证了CORL方法。

🔬 方法详解

问题定义：论文旨在解决组合序列决策问题，这类问题通常使用混合整数线性规划（MILP）建模，并通过分支定界（B&B）算法求解。然而，现有方法依赖人工设计的MILP模型，难以准确捕捉现实世界的复杂性和随机性，导致决策质量不高。此外，基于机器学习的MILP优化方法通常依赖监督学习，需要最优解作为标签，且难以有效利用MILP的梯度信息。

核心思路：论文的核心思路是将MILP的求解过程，特别是分支定界算法，视为一个可微的随机策略。这样，就可以利用强化学习（RL）直接在真实世界的数据上优化MILP模型，而无需显式地建模真实世界的复杂性。通过将MILP求解器嵌入到RL循环中，可以端到端地优化MILP的参数，从而提高决策质量。

技术框架：CORL框架的核心是将MILP求解器（通过分支定界算法）视为一个RL环境中的策略。具体来说，给定一个状态（例如，当前组合优化问题的状态），MILP求解器输出一个动作（例如，选择哪个变量进行分支）。这个动作会影响环境的状态，并产生一个奖励（例如，决策带来的收益）。RL算法（例如，策略梯度）利用这些奖励来更新MILP模型的参数，从而改进策略。整个框架包含以下主要模块：MILP模型、分支定界求解器（作为可微策略）、强化学习算法和真实世界环境。

关键创新：论文的关键创新在于将MILP求解器视为一个可微的策略，从而能够使用强化学习进行端到端的优化。这与传统的基于监督学习的MILP优化方法不同，后者需要最优解作为标签，并且难以有效利用MILP的梯度信息。CORL框架可以直接在真实世界的数据上学习，从而更好地适应实际应用中的复杂性和随机性。

关键设计：论文将分支定界算法中的分支选择规则参数化，并将其作为RL策略的一部分进行学习。奖励函数的设计至关重要，需要能够反映决策的长期影响。论文使用策略梯度算法来更新MILP模型的参数。具体的网络结构和参数设置取决于具体的应用场景，论文在一个简单的组合序列决策问题中进行了验证。

📊 实验亮点

论文在一个简单的组合序列决策问题中验证了CORL框架的有效性。实验结果表明，CORL方法能够通过强化学习有效地优化MILP模型，从而提高决策质量。虽然论文没有提供具体的性能数据和对比基线，但它证明了将MILP求解器视为可微策略并使用强化学习进行端到端优化的可行性。

🎯 应用场景

CORL框架具有广泛的应用前景，例如供应链管理、资源调度、交通运输优化等领域。通过强化学习直接优化MILP模型，可以提高决策质量，降低运营成本，并更好地适应实际应用中的复杂性和随机性。未来，CORL框架可以扩展到更复杂的MILP模型和更高级的强化学习算法，从而解决更具挑战性的组合优化问题。

📄 摘要（原文）

Combinatorial sequential decision making problems are typically modeled as mixed integer linear programs (MILPs) and solved via branch and bound (B&B) algorithms. The inherent difficulty of modeling MILPs that accurately represent stochastic real world problems leads to suboptimal performance in the real world. Recently, machine learning methods have been applied to build MILP models for decision quality rather than how accurately they model the real world problem. However, these approaches typically rely on supervised learning, assume access to true optimal decisions, and use surrogates for the MILP gradients. In this work, we introduce a proof of concept CORL framework that end to end fine tunes an MILP scheme using reinforcement learning (RL) on real world data to maximize its operational performance. We enable this by casting an MILP solved by B&B as a differentiable stochastic policy compatible with RL. We validate the CORL method in a simple illustrative combinatorial sequential decision making example.