Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning

📄 arXiv: 2310.11845v1 📥 PDF

作者: Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, Feng Wu

分类: cs.LG

发布日期: 2023-10-18

💡 一句话要点

提出强化学习框架以加速大规模线性规划的预处理

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

关键词: 线性规划 强化学习 预处理 马尔可夫决策过程 求解器优化 工业应用 机器学习

📋 核心要点

  1. 现有的预处理方法在选择、执行顺序和停止时机上依赖于专家知识，且搜索空间庞大，导致设计高质量的预处理程序极具挑战性。
  2. 本文提出的RL4Presolve框架通过强化学习将预处理程序设计任务建模为马尔可夫决策过程，能够自适应生成高质量的预处理序列。
  3. 实验结果显示，RL4Presolve在两个求解器和八个基准测试上显著提升了求解效率，尤其在工业应用中表现突出。

📝 摘要（中文）

大规模线性规划（LP）问题通常存在大量冗余，严重影响求解效率和可靠性，使得预处理成为现代LP求解器中的关键组件。如何设计高质量的预处理程序，即选择预处理器、执行顺序和停止时机，仍然是一个具有挑战性的任务。本文提出了一种简单高效的强化学习框架（RL4Presolve），将这一任务建模为马尔可夫决策过程，利用自适应动作序列同时解决上述问题。实验表明，RL4Presolve显著提高了大规模LP求解的效率，尤其是在工业基准上，且为华为供应链的部署提供了优化方案，展示了机器学习在现代求解器中的潜在经济和学术价值。

🔬 方法详解

问题定义：本文旨在解决大规模线性规划中的预处理程序设计问题。现有方法依赖于专家知识，难以适应复杂的实际场景，且搜索空间过大，导致效率低下。

核心思路：论文提出的RL4Presolve框架通过强化学习将预处理程序设计视为一个马尔可夫决策过程，利用自适应动作序列来高效生成预处理程序，从而克服传统方法的局限性。

技术框架：RL4Presolve的整体架构包括状态表示、动作选择和奖励反馈三个主要模块。状态表示捕捉当前LP问题的特征，动作选择基于强化学习策略生成预处理步骤，而奖励反馈则用于优化学习过程。

关键创新：最重要的创新在于将预处理程序设计问题转化为强化学习问题，利用自适应动作序列有效学习复杂行为，显著提高了预处理的效率和灵活性。

关键设计：在技术细节上，RL4Presolve采用了深度强化学习算法，设计了适应性强的动作空间，并通过提取学习到的策略规则来优化现有的硬编码预处理程序，确保简单高效的部署。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RL4Presolve在两个求解器（开源和商业）上对八个基准测试（包括真实和合成数据）均显著提升了求解效率，尤其是在工业基准上，提升幅度达到XX%（具体数据待补充），展示了其强大的实用性和有效性。

🎯 应用场景

该研究的潜在应用领域包括工业界的线性规划求解，尤其是在供应链管理、资源分配和生产调度等场景中。通过优化预处理程序，能够显著提升求解效率，降低计算成本，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Large-scale LP problems from industry usually contain much redundancy that severely hurts the efficiency and reliability of solving LPs, making presolve (i.e., the problem simplification module) one of the most critical components in modern LP solvers. However, how to design high-quality presolve routines -- that is, the program determining (P1) which presolvers to select, (P2) in what order to execute, and (P3) when to stop -- remains a highly challenging task due to the extensive requirements on expert knowledge and the large search space. Due to the sequential decision property of the task and the lack of expert demonstrations, we propose a simple and efficient reinforcement learning (RL) framework -- namely, reinforcement learning for presolve (RL4Presolve) -- to tackle (P1)-(P3) simultaneously. Specifically, we formulate the routine design task as a Markov decision process and propose an RL framework with adaptive action sequences to generate high-quality presolve routines efficiently. Note that adaptive action sequences help learn complex behaviors efficiently and adapt to various benchmarks. Experiments on two solvers (open-source and commercial) and eight benchmarks (real-world and synthetic) demonstrate that RL4Presolve significantly and consistently improves the efficiency of solving large-scale LPs, especially on benchmarks from industry. Furthermore, we optimize the hard-coded presolve routines in LP solvers by extracting rules from learned policies for simple and efficient deployment to Huawei's supply chain. The results show encouraging economic and academic potential for incorporating machine learning to modern solvers.