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.