用强化学习动态选列,让大规模线性规划求解快得多。
FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program
- 将选列问题建模为马尔可夫决策过程,按需选择变量数量的列
- 在切割问题和带时间窗车辆路径问题上迭代次数减少超70%
- 适合需要快速求解大规模线性规划的工业场景
列生成(CG)是求解大规模线性规划(LP)的有效迭代算法。每轮迭代中,通过添加新列来改进解。传统方法贪心地选取减少成本最负的单列,但一次添加多列又易引入冗余列。现有基于机器学习的方法因状态空间爆炸问题,每轮仅增加固定数量列。为此,我们提出快速家族列生成(FFCG)——一种基于强化学习的新型列生成方法,可在每轮按需选择变量数量的列。具体地,将列选择问题建模为马尔可夫决策过程(MDP),设计兼顾收敛速度与冗余列数的奖励函数。实验表明,FFCG在常见基准上收敛更快:在切割问题(CSP)上迭代次数减少77.1%,在带时间窗车辆路径问题(VRPTW)上减少84.8%;计算时间分别平均减少71.4%和84.0%,优于多个前沿基线方法。
原文摘要 · Abstract (English)
Column Generation (CG) is an effective and iterative algorithm to solve large-scale linear programs (LP). During each CG iteration, new columns are added to improve the solution of the LP. Typically, CG greedily selects one column with the most negative reduced cost, which can be improved by adding more columns at once. However, selecting all columns with negative reduced costs would lead to the addition of redundant columns that do not improve the objective value. Therefore, selecting the appropriate columns to add is still an open problem and previous machine-learning-based approaches for CG only add a constant quantity of columns per iteration due to the state-space explosion problem. To address this, we propose Fast Family Column Generation (FFCG) -- a novel reinforcement-learning-based CG that selects a variable number of columns as needed in an iteration. Specifically, we formulate the column selection problem in CG as an MDP and design a reward metric that balances both the convergence speed and the number of redundant columns. In our experiments, FFCG converges faster on the common benchmarks and reduces the number of CG iterations by 77.1% for Cutting Stock Problem (CSP) and 84.8% for Vehicle Routing Problem with Time Windows (VRPTW), and a 71.4% reduction in computing time for CSP and 84.0% for VRPTW on average compared to several state-of-the-art baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。