Domain-Independent Dynamic Programming (DIDP)

Domain-Independent Dynamic Programming (DIDP) is a novel model-based paradigm for combinatorial optimization based on dynamic programming (DP). In DIDP, once you formulate your problem as a DP model, you can use generic solvers to solve the model, just as in mixed-integer programming (MIP) and constraint programming (CP). DIDP shows superior performance to MIP and CP in a number of combinatorial optimization problems including vehicle routing problems (VRPs), packing problems, and scheduling problems (see our papers for detailed evaluations).

Software

Our framework is publicly available as open-source software under the MIT/Apache-2.0 license (free for commercial use!). To get started, we recommend using DIDPPy.

• DIDPPy: Python interface for DIDP. You can formulate DP models and solve them with generic solvers using Python. You do not need to install the other libraries individually.
• didp-yaml: Command line executable for DIDP taking YAML files as input. You can formulate DP models and write configurations of a solver in the YAML data format and pass them to the executable. You do not need to install the other libraries individually.
• dypdl: Rust library for DP modeling.
• dypdl-heuristic-search: Rust library for heuristic search based generic DP solvers.

All of the above software are managed on our GitHub repository.

Software Using DIDP

• Discrete Optimization: a Python library providing models and solvers for combinatorial optimization problems such as routing and scheduling, maintained by Airbus. It uses DIDPPy as one of the backends.

Modeling in DIDP

We use Dynamic Programming Description Language (DyPDL) as a modeling formalism for DIDP, which is based on state transition systems. While it is named “Language”, DyPDL is independent from particular programming languages or data formats, and we provide Python, Rust, and YAML interfaces for it.

We provide Python and YAML models used by our papers in a repository.

Solvers for DIDP

Currently, our generic DIDP solvers are based on heuristic search such as A* and beam search, inspired by AI planning.

Papers

• Ryo Kuroiwa and J. Christopher Beck. Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization. In Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS). 2023. supplement slides poster
  • This paper introduces the notion of DIDP with the modeling language DyPDL and the generic solver CAASDy with the experimental evaluation using 6 combinatorial optimization problems.
• Ryo Kuroiwa and J. Christopher Beck. Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search. In Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS). 2023. supplement slides
  • This paper proposes 6 anytime solvers for DIDP with the experimental evaluation using 9 combinatorial optimization problems.
• Ryo Kuroiwa and J. Christopher Beck. Large Neighborhood Beam Search for Domain-Independent Dynamic Programming. In Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming (CP). 2023. slides poster
  • This paper proposes a large neighborhood search framework for DIDP based on beam search.
• Ryo Kuroiwa and J. Christopher Beck. Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming. In Proceedings of the 38th Annual AAAI Conference on Artificial Intelligence (AAAI). 2024. supplement slides poster
  • This paper develops multi-thread DIDP solvers based on parallel beam search algorithms.
  • Errata: In Algorithm 8, |L| < k should be added in the while loop condition. This condition is used in the implementation but was forgotten in the pseudo-code.
• Ryo Kuroiwa and J. Christopher Beck. Domain-Independent Dynamic Programming
  • This paper formally defines and theoretically analyzes DyPDL and heuristic search solvers for DIDP, extending the two ICAPS papers. The experimental evaluation uses 11 combinatorial optimization problems.

Papers using DIDP

• Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck. Optimization Models for Pickup and Delivery Problems with Reconfigurable Capacities. In Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming (CP). 2023.
  • DIDP beats MIP and CP in a pickup and delivery problem with complicated capacity constraints inspired by a real-world application.
• Jiacheng Zhang and J. Christopher Beck. Solving LBBD Master Problems with Constraint Programming and Domain-Independent Dynamic Programming. In Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming (CP). 2024.
  • This paper proposes a Bender’s decomposition method using DIDP as a master problem formulation.
• Jiacheng Zhang and J. Christopher Beck. Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups. INFORMS Journal on Computing 2024. post-print
  • DIDP models for SUALBP-1 and SUALBP-2, variants of assembly line balancing problems, are proposed, and they outperform MIP and CP models.

Presentations

• Introduction to DIDP presented at the DPSOLVE workshop at CP 2023

Contact Information

Ryo Kuroiwa (kuroiwa [at] nii.ac.jp)