用机器学习提升路径规划求解速度,稳定且不损失精度。
Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation

- 通过学习双变量顺序关系,动态构建优化约束
- 在两类车辆路径问题上提速超90%,平均解差不足1%
- 适合需要快速求解大规模路径优化的工业场景
列生成(CG)是解决大规模优化问题的核心方法,但其对偶解不稳定会显著拖慢收敛。现有深度对偶最优不等式依赖特定问题的交换论证,难以应用于带容量、时间窗等资源约束的路径问题。本文提出学习型成对深度对偶最优不等式(L-PDDOIs),通过采样最优对偶解,自动筛选在大量样本中共现的双变量顺序关系,并训练分类器预测这些关系,再经图结构后处理去重过滤后引入主问题。进一步设计恢复机制,可选择性松弛学习到的不等式,并在基线对偶界恢复时提供证明。在容量限制车辆路径问题和带时间窗车辆路径问题的标准测试集上,直接部署L-PDDOIs使几何均值根列生成时间分别减少89.7%和93.9%,平均目标值损失仅1.3%和0.5%;恢复机制仍保持54.8%和83.1%的时间提升,且保证对偶界无损。
原文摘要 · Abstract (English)
Column generation (CG) is central to many large-scale optimization algorithms, including branch-price-and-cut methods for vehicle routing problems, but unstable dual solutions can substantially slow its convergence. Existing deep dual-optimal inequalities can reduce this instability by restricting the dual space. Their construction, however, typically relies on problem-specific exchange arguments that are difficult to establish for routing problems with capacity limits, time windows, and other resource constraints. We introduce learned pairwise deep dual-optimal inequalities (L-PDDOIs), a learning framework that predicts pairwise orderings between dual variables and incorporates their primal counterparts directly into the master problem. To construct training labels, the framework samples optimal dual solutions and selects pairwise order relations that hold simultaneously on a sufficiently large common subset of the samples. A classifier then assigns a score to each candidate relation. Because conflicts and redundancies among the predicted relations can impair performance, graph-based postprocessing filters and compresses the candidate set before deployment. We further introduce a recovery procedure that selectively relaxes learned inequalities and provides a certificate when the baseline CG bound has been restored. On the main test sets for the capacitated vehicle routing problem and the vehicle routing problem with time windows, direct deployment of L-PDDOIs reduces the geometric mean root CG time by 89.7% and 93.9%, respectively, while incurring mean bound losses of only 1.3% and 0.5%. The recovery procedure retains corresponding time reductions of 54.8% and 83.1%, respectively, while guaranteeing no loss in the CG bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。