  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.
