论文标题
独立于域的动态编程：对组合优化的通用状态空间搜索
Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
论文作者
论文摘要
对于组合优化问题，基于模型的方法，例如混合成员编程（MIP）和约束编程（CP），旨在解除建模和解决问题：声明性问题解决的“圣杯”。我们建议基于动态编程（DP）的新型基于模型的范例，这是独立于域的动态编程（DIDP）。尽管DP并不是新事物，但通常已作为特定于问题的方法实现。我们提出了动态编程说明语言（DYPDL），这是一种定义DP模型的形式主义，并为DYPDL（CAASDY）开发成本代数A*求解器，这是使用状态空间搜索的通用求解器。我们将现有的特定问题的DP和状态空间搜索方法形式化为组合优化问题，为DYPDL中的DP模型。使用Caasdy和Commercial Mip和CP求解器，我们通过实验将DP模型与现有的MIP和CP模型进行比较，表明尽管具有新生的性质，但Caasdy在许多常见的问题类别上都比MIP和CP胜过MIP和CP。
For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the 'holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a new model-based paradigm based on dynamic programming (DP). While DP is not new, it has typically been implemented as a problem-specific method. We propose Dynamic Programming Description Language (DyPDL), a formalism to define DP models, and develop Cost-Algebraic A* Solver for DyPDL (CAASDy), a generic solver for DyPDL using state space search. We formalize existing problem-specific DP and state space search methods for combinatorial optimization problems as DP models in DyPDL. Using CAASDy and commercial MIP and CP solvers, we experimentally compare the DP models with existing MIP and CP models, showing that, despite its nascent nature, CAASDy outperforms MIP and CP on a number of common problem classes.
