# Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 45 references that are in the map.
- First posted on arXiv 26 Nov 2022.

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

- [Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2401.13883/) (2024)
- [Time Series Supplier Allocation via Deep Black-Litterman Model](https://mlsanity.com/paper/2401.17350/) (2024)
- [Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2503.16371/) (2025)
- [Domain-Independent Dynamic Programming with Constraint Propagation](https://mlsanity.com/paper/2603.16648/) (2026)
- [Column Generation with Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2510.14317/) (2025)
- [A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem](https://mlsanity.com/paper/2512.15198/) (2025)
- [CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem](https://mlsanity.com/paper/2605.23569/) (2026)

## Abstract (arXiv)

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.