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 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.

📄 PDF Abstract BibTeX arXiv:2401.13883

Code (2)

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

kurorororo/didp-models 공식 구현

Tasks

Combinatorial OptimizationHeuristic Search

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…

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

Combinatorial Optimization

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…

Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

2023-05-31 · NeurIPS 2023 11 · Jacobus G. M. van der Linden, Mathijs M. de Weerdt, Emir Demirović

Global optimization of decision trees has shown to be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpose solvers for which scalabilit…

global-optimization