Domain-Independent Dynamic Programming with Constraint Propagation
Authors: Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa
Organizations: Delft University of Technology, The Netherlands · University of Toronto, Canada · National Institute of Informatics, Japan · The Graduate University for Advanced Studies, SOKENDAI, Japan
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.
Figures & tables
Figure 1: An overview of the interactions in our framework.
Figure 2: Number of 1∣ri,δi∣∑wiTi instances solved compared to the number of state expansions and time.
Figure 3: Number of 1∣ri,δi∣∑wiTi instances solved over ϕ . The marked parts are instances proven infeasible and the unmarked parts are instances proven optimal. Our approach solves the most instances when they are tightly constrained.
Figure 4: Number of RCPSP instances solved compared to the number of state expansions and time.
Figure 5: Number of TSPTW instances solved compared to the number of state expansions and time.
Figure 6: Number of solved TSPTW Rifki and Solnon ( 2025 ) instances across α . The marked parts are instances proven infeasible and the unmarked parts are instances proven optimal. The lower plot uses an extended set of instances to show 1.0≤α≤1.5 . Our approach solves the most instances when they are tightly constrained.
Figure 7: Number of solved TSPTW Rifki and Solnon ( 2025 ) instances ( 1.0≤α≤1.5 ) over state expansions. Our approach solves the most instances per expansion.
Figure 8: Comparison of state expansions on TSPTW Rifki and Solnon ( 2025 ) instances ( 1.0≤α≤1.5 ). Our approach reduces the number of expansions by orders of magnitude.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: Average optimality gap over the number of state expansions and time for 1∣ri,δi∣∑wiTi instances.
Figure 10: Average optimality gap over the number of state expansions and time for RCPSP instances.
Figure 11: Comparison of optimality gap on RCPSP instances. Our approach improves the optimality gap of OR-Tools for numerous instances.
Figure 12: Average optimality gap over the number of state expansions and time for TSPTW instances.
Figure 13: Average optimality gap over the number of state expansions and time for TSPTW instances by Rifki and Solnon ( 2025 ) where 1.0≤α≤1.5 .
Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan