Domain-Independent Dynamic Programming

Session date: 3 June 2024

Session host: Koos van der Linden

Summary:

The authors present a domain-independent dynamic programming (DP) approach that allows to model DP solutions in a similar way as MIP and CP. In their benchmark of six combinatorial problems (including TSPTW, bin packing, and CVRP) their method can solve more problems to optimality for several domains than CP and MIP. The main limitation for now is memory.

Relevant papers

  1. Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
    Ryo Kuroiwa, and J. Christopher Beck
    Proceedings of the International Conference on Automated Planning and Scheduling, Jul 2023
    HTML