For combinatorial optimization problems, model-based paradigms 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 introduce
Dynamic Programming Description Language (DyPDL), a formalism to define DP
models based on a state transition system, inspired by AI planning. We show
that heuristic search algorithms can be used to solve DyPDL models and propose
seven DIDP solvers. We experimentally compare our DIDP solvers with commercial
MIP and CP solvers (solving MIP and CP models, respectively) on common
benchmark instances of eleven combinatorial optimization problem classes. We
show that DIDP outperforms MIP in nine problem classes, CP also in nine problem
classes, and both MIP and CP in seven.

基于动态规划 (DP) 的领域无关动态规划 (DIDP) 模型具有优于其他方法的性能，通过引入七种 DIDP 求解器和对 11 种组合优化问题类别的基准测试，实验证明 DIDP 在大部分问题类别中优于混合整数规划 (MIP) 和约束规划 (CP)。