提出新方法自动判断何时重解复杂优化问题,省时又省钱。
Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving
- 结合变化点检测与近端策略优化,智能决策重解时机
- 在8个真实和合成数据集上性能优于基线2%-17%
- 适合高频率实时优化场景,填补实时MILP评估空白
实时运营中常面临是否重解优化问题的抉择。尽管数据平台可高频采集信息,但许多实时任务需反复求解计算量大的混合整数线性规划(MILP)问题。何时重解成为关键经济问题。现有方法在刻画解的质量与求解成本、检测环境变化、选择有益样本方面存在挑战,且对常见NP-hard MILP关注不足。本文提出基于变化点检测的近端策略优化框架(POC),系统平衡性能与成本。理论分析建立了重解次数与求解成本的关系。在8个合成与真实数据集上测试表明,POC持续优于现有基线2%-17%。此外,本工作首次构建了实时MILP基准数据集与评估标准,填补研究空白。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。