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

  • This paper introduces the paradigm of DIDP, CAASDy, and DIDP models for TSPTW, the capacitated vehicle routing problem (CVRP), bin packing, the simple assembly line balancing problem (SALBP-1), MOSP, and graph-clear.

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

  • This paper introduces anytime solvers for DIDP including CABS and DIDP models for the multi-commodity pick-and-delivery traveling salesperson problem (m-PDTSP), the talent scheduling problem, and the single machine scheduling to minimize total weighted tardiness (\(1||\sum w_iT_i\)).

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

  • This paper introduces Large Neighborhood Beam Search (LNBS).

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

  • This paper parallelizes CABS.

• Ryo Kuroiwa and J. Christopher Beck. Domain-Independent Dynamic Programming. arXiv. 2024.

  • This paper provides formal definitions of the modeling language and solvers for DIDP. It also introduces DIDP models for the orienteering problem with time windows and the multi-dimensional knapsack problem.

• 10. Christopher Beck, Ryo Kuroiwa, Jimmy H.M. Lee, Peter J. Stuckey, and Allen Z. Zhong. Transition Dominance in Domain-Independent Dynamic Programming. In Proceedings of the 31st International Conference on Principles and Practice of Constraint Programming (CP).

  • This paper introduces state functions and transition dominance.