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

2022-11-26 · Ryo Kuroiwa, J. Christopher Beck

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.

📄 PDF Abstract BibTeX arXiv:2211.14409

Code (1)

domain-independent-dp/didp-rs 공식 구현

Tasks

Combinatorial Optimization

Column Generation Using Domain-Independent Dynamic Programming

2025-10-16 · Ryo Kuroiwa, Edward Lam arxiv

Column generation and branch-and-price are leading methods for large-scale exact optimization. Column generation iterates between solving a master problem and a pricing problem. The master problem is a linear program, wh…

GP-HD: Using Genetic Programming to Generate Dynamical Systems Models for Health Care

2019-04-11 · Mark Hoogendoorn, Ward van Breda, Jeroen Ruwaard

The huge wealth of data in the health domain can be exploited to create models that predict development of health states over time. Temporal learning algorithms are well suited to learn relationships between health state…

Domain-Independent Dynamic Programming

2024-01-25 · Ryo Kuroiwa, J. Christopher Beck

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 probl…

Combinatorial Optimization Heuristic Search

Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming

2025-03-20 · Minori Narita, Ryo Kuroiwa, J. Christopher Beck

Domain-Independent Dynamic Programming (DIDP) is a state-space search paradigm based on dynamic programming for combinatorial optimization. In its current implementation, DIDP guides the search using user-defined dual bo…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Domain-Independent Dynamic Programming with Constraint Propagation

2026-03-17 · Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa arxiv

There are two prevalent model-based paradigms for combinatorial problems: 1) state-based representations, such as heuristic search, dynamic programming (DP), and decision diagrams, and 2) constraint and domain-based repr…