arXiv:2510.14317math.OCcs.AI2025-10被引 1

用通用动态规划解决优化问题中的列生成,提升效率与适用性。

Column Generation with Domain-Independent Dynamic Programming

  • 采用无领域依赖的动态规划作为通用列生成求解器
  • 在四类问题中性能优于现有自动列生成工具及传统整数规划方法
  • 适合需要快速部署列生成框架的研究者与工程师

列生成与分支定价(B&P)是大规模精确优化的主流方法,通过迭代求解主问题与定价问题实现。由于离散优化的复杂性,高性能列生成通常依赖针对特定问题结构定制的定价算法,导致该方法具有强问题特异性,难以通用化。本文表明,无领域依赖动态规划(DIDP)——一种基于模型的动态规划范式,可作为通用定价求解器。我们为DIDP开发了新的建模特性与求解算法,在典型定价问题中实现更优性能。实验显示,在四类问题上,基于DIDP的B&P实现,其表现优于现有的自动化B&P求解器,以及使用混合整数规划或约束规划进行定价的B&P方法。

原文摘要 · Abstract (English)

Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem's structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.

列生成动态规划优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。