Domain-Independent Dynamic Programming
This provides a new declarative solving approach for combinatorial optimization, potentially benefiting researchers and practitioners in operations research and AI, though it builds on existing dynamic programming concepts.
The authors tackled the challenge of creating a model-based paradigm for combinatorial optimization by proposing domain-independent dynamic programming (DIDP), which outperformed commercial MIP and CP solvers in nine out of eleven problem classes and both in seven.
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 novel 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 artificial intelligence (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. DIDP also achieves superior performance to existing state-based solvers including domain-independent AI planners.