# Domain-Independent Dynamic Programming

arXiv: https://arxiv.org/abs/2401.13883 · HTML: https://mlsanity.com/paper/2401.13883/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 157 references that are in the map.
- First posted on arXiv 25 Jan 2024.

## Builds on (most cited first, 9 of 9)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization](https://mlsanity.com/paper/2211.14409/) (2022)
- [SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning](https://mlsanity.com/paper/2102.09193/) (2021)
- [Iterative beam search algorithms for the permutation flowshop](https://mlsanity.com/paper/2009.05800/) (2020)
- [Improving the filtering of Branch-And-Bound MDD solver (extended)](https://mlsanity.com/paper/2104.11951/) (2021)
- [An Enhanced Branch-and-bound Algorithm for the Talent Scheduling Problem](https://mlsanity.com/paper/1401.5869/) (2014)
- [Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection](https://mlsanity.com/paper/2211.13118/) (2022)
- [An Ant Colony System for the Team Orienteering Problem with Time Windows](https://mlsanity.com/paper/2305.07305/) (2023)

## Built on by (most cited first, 3 of 3)

- [Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2503.16371/) (2025)
- [Column Generation with Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2510.14317/) (2025)
- [Optimal Planning in a Dynamic World](https://mlsanity.com/paper/2610.03312/) (2026)

## Abstract (arXiv)

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.