用强化学习优化分支定界求解混合整数规划，提升实际决策性能。
CORL: Reinforcement Learning of MILP Policies Solved via Branch and Bound
- 将分支定界求解的MILP视为可微随机策略，实现端到端强化学习训练。
- 在真实数据上训练后，决策性能优于传统建模方法。
- 适合需要高实际表现的组合优化场景，如物流、调度。
组合顺序决策问题通常建模为混合整数线性规划（MILP）并使用分支定界（B&B）算法求解。然而，准确建模现实世界中具有随机性的复杂问题存在困难，导致实际表现不佳。近期机器学习方法被用于构建以决策质量为目标而非精确建模真实问题的MILP模型，但这些方法通常依赖监督学习，假设可获取最优决策，并使用代理替代MILP梯度。本文提出一个概念验证框架CORL，通过在真实数据上使用强化学习（RL）端到端微调MILP方案，以最大化其运营性能。我们通过将由B&B求解的MILP建模为兼容强化学习的可微随机策略来实现这一目标。在简单的组合顺序决策示例中验证了CORL方法的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。