Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving

📄 arXiv: 2509.23470v1 📥 PDF

作者: Rui Ai, Hugo De Oliveira Barbalho, Sirui Li, Alexei Robsky, David Simchi-Levi, Ishai Menache

分类: cs.LG

发布日期: 2025-09-27

💡 一句话要点

提出POC框架，通过策略学习优化代价敏感的MILP重求解问题

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

关键词: 混合整数线性规划 强化学习 近端策略优化 变化点检测 实时优化

📋 核心要点

  1. 实时运营中频繁求解计算密集型MILP问题，现有方法在平衡求解成本和性能方面存在不足。
  2. 提出POC框架，结合近端策略优化和变化点检测，系统地解决MILP重求解时机选择问题。
  3. 在合成和真实数据集上验证，POC框架性能优于现有基线2%-17%，并提供实时MILP基准。

📝 摘要（中文）

在实时运营中，一个常见的挑战是决定何时重新求解优化问题，以及何时继续使用现有解决方案。虽然现代数据平台可以高频率地收集信息，但许多实时运营需要重复求解计算密集型的混合整数线性规划（MILP）问题。因此，确定何时重新求解是一个具有重要经济价值的问题。这个问题带来了几个挑战：1）如何表征解的最优性和求解成本；2）如何检测环境变化并选择有益的样本来求解MILP；3）鉴于较长的时间范围和非MDP结构，传统的强化学习（RL）方法无法直接应用，并且容易出现价值函数爆炸。现有文献主要关注启发式方法、低数据设置和平滑目标，很少关注常见的NP-hard MILP。我们提出了一个名为Proximal Policy Optimization with Change Point Detection（POC）的框架，该框架系统地提供了一种解决方案，用于在决定适当的重求解时间时平衡性能和成本。理论上，我们建立了重求解次数与重求解成本之间的关系。为了测试我们的框架，我们组装了八个合成和真实世界的数据集，并表明POC始终优于现有基线2%-17%。作为一项额外的好处，我们的工作通过引入实时MILP基准和评估标准填补了文献中的空白。

🔬 方法详解

问题定义：论文旨在解决实时运营中，何时重新求解混合整数线性规划（MILP）以达到性能和成本的最佳平衡问题。现有方法，如启发式算法，在处理NP-hard MILP问题时效果不佳，且缺乏对求解成本的系统考虑。传统强化学习方法在长时域和非马尔可夫决策过程（non-MDP）结构下，容易出现价值函数爆炸问题。

核心思路：论文的核心思路是利用强化学习来学习一个策略，该策略能够根据环境变化和求解成本，动态地决定何时重新求解MILP。通过学习，该策略能够权衡求解带来的性能提升和求解所消耗的计算资源，从而在性能和成本之间找到最佳平衡点。

技术框架：POC框架包含以下主要模块：1）环境状态表示：对环境变化进行建模，包括问题参数的变化等；2）变化点检测：检测环境是否发生显著变化，从而触发重新求解的决策；3）近端策略优化（PPO）：使用PPO算法学习一个策略，该策略根据环境状态和变化点检测结果，决定是否重新求解MILP；4）奖励函数设计：设计合适的奖励函数，鼓励策略在性能提升和求解成本之间进行权衡。

关键创新：POC框架的关键创新在于：1）将变化点检测与强化学习相结合，能够更有效地检测环境变化，并根据变化情况调整求解策略；2）使用近端策略优化（PPO）算法，避免了传统强化学习方法中的价值函数爆炸问题；3）系统地考虑了求解成本，并在奖励函数中对其进行建模，从而实现了性能和成本之间的平衡。

关键设计：POC框架的关键设计包括：1）变化点检测的阈值设置，需要根据具体问题进行调整；2）PPO算法的参数设置，如学习率、折扣因子等，需要进行调优；3）奖励函数的设计，需要仔细考虑性能提升和求解成本之间的权重关系。论文中具体使用了哪些网络结构和损失函数等细节信息未知。

📊 实验亮点

实验结果表明，POC框架在八个合成和真实世界的数据集上，始终优于现有基线2%-17%。这表明POC框架能够有效地平衡性能和成本，并在实时MILP求解问题上取得显著的性能提升。此外，该研究还提供了实时MILP基准和评估标准，为后续研究提供了参考。

🎯 应用场景

该研究成果可广泛应用于需要实时求解MILP的场景，如供应链管理、交通运输、能源调度等。通过POC框架，企业可以更有效地利用计算资源，在保证运营性能的同时，降低求解成本。该研究为实时优化决策提供了一种新的思路，具有重要的实际应用价值和未来发展潜力。

📄 摘要（原文）

A common challenge in real-time operations is deciding whether to re-solve an optimization problem or continue using an existing solution. While modern data platforms may collect information at high frequencies, many real-time operations require repeatedly solving computationally intensive optimization problems formulated as Mixed-Integer Linear Programs (MILPs). Determining when to re-solve is, therefore, an economically important question. This problem poses several challenges: 1) How to characterize solution optimality and solving cost; 2) How to detect environmental changes and select beneficial samples for solving the MILP; 3) Given the large time horizon and non-MDP structure, vanilla reinforcement learning (RL) methods are not directly applicable and tend to suffer from value function explosion. Existing literature largely focuses on heuristics, low-data settings, and smooth objectives, with little focus on common NP-hard MILPs. We propose a framework called Proximal Policy Optimization with Change Point Detection (POC), which systematically offers a solution for balancing performance and cost when deciding appropriate re-solving times. Theoretically, we establish the relationship between the number of re-solves and the re-solving cost. To test our framework, we assemble eight synthetic and real-world datasets, and show that POC consistently outperforms existing baselines by 2%-17%. As a side benefit, our work fills the gap in the literature by introducing real-time MILP benchmarks and evaluation criteria.