arXiv:2511.12986cs.LGcs.AI2025-11AAAI

用强化学习训练更通用的分支策略,提升大规模整数规划求解效率。

Learning Branching Policies for MILPs with Proximal Policy Optimization

  • 采用近端策略优化算法,从零开始训练分支策略,避免过拟合专家示范。
  • 在分布外实例上减少搜索节点数,改善原对偶积分指标,提升求解鲁棒性。
  • 适合需要处理多样化问题实例的优化求解系统开发者参考。

分支定界法(B& B)是求解混合整数线性规划(MILP)的主要精确方法,但其指数时间复杂度对大规模实例构成挑战。近年来机器学习的发展推动了数据驱动分支策略的研究。然而,现有方法多依赖模仿学习(IL),易过拟合专家示范,在结构差异大或未见实例上泛化能力差。本文提出树门近端策略优化(TGPPO),一种基于强化学习(RL)的新型框架,利用近端策略优化(PPO)训练分支策略,以提升在异构MILP实例间的泛化能力。该方法基于参数化状态空间表示,动态捕捉搜索树演进中的上下文信息。实验表明,TGPPO在减少探索节点数和改进原对偶积分(PDI)方面,优于现有学习型策略,尤其在分布外实例上表现突出。结果表明,强化学习有望构建鲁棒、可适应的MILP分支策略。

原文摘要 · Abstract (English)

Branch-and-Bound (B\&B) is the dominant exact solution method for Mixed Integer Linear Programs (MILP), yet its exponential time complexity poses significant challenges for large-scale instances. The growing capabilities of machine learning have spurred efforts to improve B\&B by learning data-driven branching policies. However, most existing approaches rely on Imitation Learning (IL), which tends to overfit to expert demonstrations and struggles to generalize to structurally diverse or unseen instances. In this work, we propose Tree-Gate Proximal Policy Optimization (TGPPO), a novel framework that employs Proximal Policy Optimization (PPO), a Reinforcement Learning (RL) algorithm, to train a branching policy aimed at improving generalization across heterogeneous MILP instances. Our approach builds on a parameterized state space representation that dynamically captures the evolving context of the search tree. Empirical evaluations show that TGPPO often outperforms existing learning-based policies in terms of reducing the number of nodes explored and improving p-Primal-Dual Integrals (PDI), particularly in out-of-distribution instances. These results highlight the potential of RL to develop robust and adaptable branching strategies for MILP solvers.

强化学习整数规划分支策略优化求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。