用强化学习直接解列生成中的定价问题，提速显著
Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing
- 基于注意力机制的强化学习模型端到端求解定价问题
- 在车辆路径问题上，运行时间大幅缩短，目标差距合理
- 无需启发式辅助，适合大规模组合优化场景
本文研究利用强化学习（RL）解决列生成（CG）中的定价问题（PP）。提出一种基于注意力机制的RL模型，直接端到端求解具有最小负缩减成本的列，无需依赖任何启发式方法。以车辆路径问题（VRP）为案例，通过实验对比基于动态规划（DP）的启发式算法，结果表明该方法在显著更短的运行时间内，能以合理的目标差距求解线性松弛问题。
原文摘要 · Abstract (English)
In this paper, we address the problem of Column Generation (CG) using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a set of experiments where our method is compared against a Dynamic Programming (DP)-based heuristic for solving the PP, we show that our method solves the linear relaxation up to a reasonable objective gap in significantly shorter running times.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。