EUVIMEDEUVIMED entdecken
Crossref

Domain-Independent Dynamic Programming with Constraint Propagation

Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa

Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 171-180

DOI: 10.1609/icaps.v36i1.42826 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Imko Marijnissen und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 representations, such as constraint programming (CP), (mixed-)integer programming, and Boolean satisfiability. In this paper, we bridge the gap between the DP and CP paradigms by integrating constraint propagation into DP, enabling a DP solver to prune states and transitions using constraint propagation. To this end, we implement constraint propagation using a general-purpose CP solver in the Domain-Independent Dynamic Programming framework and evaluate using heuristic search on three combinatorial optimisation problems: Single Machine Scheduling with Time Windows, the Resource Constrained Project Scheduling Problem (RCPSP), and the Travelling Salesperson Problem with Time Windows (TSPTW). Our evaluation shows that constraint propagation significantly reduces the number of state expansions, causing our approach to solve more instances than a DP solver for Single Machine Scheduling and RCPSP, and showing similar improvements for tightly constrained TSPTW instances. The runtime performance indicates that the benefits of propagation outweigh the overhead for constrained instances, but that further work into reducing propagation overhead could improve performance further. Our work is a key step in understanding the value of constraint propagation in DP solvers, providing a model-based approach to integrating DP and CP.

Zitieren

APA

Marijnissen, I., Beck, J. C., Demirović, E., & Kuroiwa, R. (2026). Domain-Independent Dynamic Programming with Constraint Propagation. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 171-180. https://doi.org/10.1609/icaps.v36i1.42826

Vancouver

Marijnissen I, Beck JC, Demirović E, Kuroiwa R. Domain-Independent Dynamic Programming with Constraint Propagation. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):171-180. doi:10.1609/icaps.v36i1.42826

BibTeX
@article{Marijnissen2026,
  author = {Marijnissen, Imko and Beck, J. Christopher and Demirović, Emir and Kuroiwa, Ryo},
  title = {Domain-Independent Dynamic Programming with Constraint Propagation},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {171--180},
  doi = {10.1609/icaps.v36i1.42826}
}
Kostenlos starten →