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 .
Dynamic Programming (DP) and Constraint Programming (CP) are well-established paradigms for solving combinatorial optimization problems. Usually, these two approaches are used separately. This paper aims to show that the two can be combined effectively and elegantly, with DP serving as the primary search framework and CP used as a subroutine to leverage global constraint propagation. This paper presents such an approach for the Partial Shop Scheduling Problem (PSSP), for which a pure DP method has previously been proposed, and efficient CP filtering algorithms are available. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints. The approach is flexible enough to accommodate anytime DP strategies, such as anytime column search, whereas the original DP algorithm operated in a strictly layer-wise manner. Moreover, the flexibility of the CP modeling makes it straightforward to incorporate arbitrary precedence constraints. As a result, the model naturally handles any precedence graph and even enables the design of a Large Neighborhood Search (LNS) scheme, in which the DP model is reused, and partial-order schedules are imposed across restarts to improve the incumbent solution. While not competitive with state-of-the-art pure CP solvers for this specific problem, our primary contribution is demonstrating the viability of this hybrid integration.
Cumulative constraints are central in scheduling with constraint programming, yet propagation is typically performed per constraint, missing multi-resource interactions and causing severe slowdowns on some benchmarks. I present a preprocessing method for inferring additional cumulative constraints that capture such interactions without search-time probing. This approach interprets cumulative constraints as linear inequalities over occupancy vectors and generates valid inequalities by (i) discovering covers, the sets of tasks that cannot run in parallel, (ii) strengthening the cover inequalities for the discovered sets with lifting, and (iii) injecting the resulting constraints back into the scheduling problem instance. Experiments on standard RCPSP and RCPSP/max test suites show that these inferred constraints improve search performance and tighten objective bounds on favorable instances, while incurring little degradation on unfavorable ones. Additionally, these experiments discover 25 new lower bounds and five new best solutions; eight of the lower bounds are obtained directly from the inferred constraints.
Konstantin Sidorov
Faculty of Electrical Engineering, Mathematics & Computer Science, Delft University of Technology, Delft, The Netherlands
Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem's structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.
Ryo Kuroiwa, Edward Lam
Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan