Paper deep dive
Domain-Independent Dynamic Programming with Constraint Propagation
Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/22/2026, 5:44:35 AM
Summary
The paper introduces a framework for integrating constraint propagation into Domain-Independent Dynamic Programming (DIDP) to bridge the gap between state-based DP and constraint-based CP paradigms. By utilizing a general-purpose CP solver within the DIDP framework, the approach enables pruning of states and transitions, significantly reducing state expansions in combinatorial optimization problems like Single Machine Scheduling, RCPSP, and TSPTW.
Entities (6)
Relation Signals (3)
DIDP framework → evaluateson → Single Machine Scheduling
confidence 98% · We evaluate our framework on three combinatorial problems: Single Machine Schedule with Time Windows
Domain-Independent Dynamic Programming → integrates → Constraint Programming
confidence 95% · In this paper, we bridge the gap between the DP and CP paradigms by integrating constraint propagation into DP
Constraint propagation → reduces → state expansions
confidence 95% · Our evaluation shows that constraint propagation significantly reduces the number of state expansions
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2603.16648v1
- Canonical: https://arxiv.org/abs/2603.16648v1
Trouble viewing inline? Open PDF directly →
Full Text
73,355 characters extracted from source content.
Expand or collapse full text
Domain-Independent Dynamic Programming with Constraint Propagation Imko Marijnissen1, J. Christopher Beck2, Emir Demirović1, Ryo Kuroiwa3 Abstract 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 (1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i), 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 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i 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. Code — https://doi.org/10.5281/zenodo.19051392 Experiments — https://doi.org/10.5281/zenodo.19051248 1 Introduction Combinatorial optimisation is key in Artificial Intelligence (AI), encompassing problems such as planning, scheduling, and variants of satisfiability. Within this field, Dynamic Programming (DP) and Constraint Programming (CP) provide declarative model-based frameworks such as Domain-Independent Dynamic Programming (Kuroiwa and Beck 2023a, 2025a) and MiniZinc (Nethercote et al. 2007; Stuckey et al. 2014) that enable users to formulate mathematical representations of problems that can then be solved by generic solvers. While solving the same problem, the techniques used by solvers following these paradigms differ. DP solvers focus on heuristic search with dual bounds, using a state-based problem representation which facilitates duplicate detection and dominance detection techniques. In contrast, CP solvers focus on using depth-first search and inference techniques to prune the search space by determining which values cannot be assigned to variables in a solution. In this work we focus on DP solvers using heuristic search, as opposed to decision diagram branch-and-bound (Bergman et al. 2016), used by decision diagram solvers such as ddo (Gillard et al. 2020) and CODD (Michel and van Hoeve 2024). Previous works introduce constraint propagation in DP approaches, but they either only used problem-specific propagation (Fontaine et al. 2023; brița2025optimal), or did not use heuristic search (Tanaka and Fujikuma 2012). Other, related but orthogonal, work has focused on using dominance and caching (Chu and Stuckey 2015; Chu et al. 2010; Smith 2005) in a CP solver. To the best of our knowledge, no work has been done on integrating generic constraint propagation in a model-based DP framework. To address this gap, we create a framework for integrating constraint propagation from CP with DP modelling and implement our approach using general-purpose CP and DP solvers, providing: 1. A dual view of the problem, using a state-based DP view and an integer-based CP view, which provides: • Dominance and duplicate detection, and heuristic search using the DP view of the problem. • Strong inference techniques for constraints using the CP view of the problem, allowing pruning of states and strengthening of the dual bound. 2. A generic model-based way of integrating heuristic search with constraint propagation, allowing any form of constraint propagation rather than only relying on domain-specific inference techniques (though these techniques are supported by our framework as well). We evaluate our framework on three combinatorial problems: Single Machine Schedule with Time Windows (1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i), the Resource Constrained Project Scheduling Problem (RCPSP), and the Travelling Salesperson Problem with Time Windows (TSPTW). For these problems, we show that constraint propagation significantly reduces the number of state expansions, enabling our approach to solve more instances than a DP solver alone for 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i and RCPSP, and tightly constrained TSPTW instances. The performance in terms of runtime indicates that the benefits of propagation outweigh the overhead for tightly constrained instances, but that further work into reducing the propagation time is needed. In our in-depth analysis, we vary 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i and TSPTW instance constrainedness, demonstrating that propagation performs exceptionally well when instances are highly constrained. This work provides a key step in ascertaining the usefulness of constraint propagation in DP solvers using heuristic search, allowing us to better understand the complementary strengths and weaknesses of the approaches. 2 Preliminaries We introduce the necessary concepts related to dynamic programming, the Domain-Independent Dynamic Programming (DIDP) framework and its Rust interface, heuristic search in DIDP, and constraint programming. 2.1 Domain-Independent Dynamic Programming Dynamic Programming (DP) is a problem-solving methodology based on state-based representations. Domain-Independent Dynamic Programming (DIDP) is a model-based framework for solving combinatorial optimisation problems formulated as DP models. One of its strengths is that DIDP models can be solved using generic solvers, removing the need to implement specialised algorithms for each DP model. It has recently seen success on combinatorial problems, such as single machine scheduling and TSPTW (Kuroiwa and Beck 2023b). A DIDP model is a state-transition system where a solution is created by starting with a target state 0S^0 and applying a sequence of transitions until a base state is reached. A successor state ⟦τ⟧S_ τ is created from S by applying a possible transition τ∈T()τ (S) with weight wτ()w_τ(S). The cost of a solution is the sum of transition weights plus the cost of the base state, where V(S) maps S to its optimal solution cost and the dual bound is a lower (upper) bound on V(S) in minimisation (maximisation) problems. Thus, the goal of a DIDP solver is to compute V(0)V(S^0). While the DIDP framework allows the user to solve generic DP models, it is limited in its expressivity due to the restrictions of its declarative modelling language, Dynamic Programming Problem Description Language (DyPDL). The Rust Programmable Interface for DIDP (RPID) defines a DIDP model in terms of Rust functions, allowing the user to define more complex dual bounds, state constraints and/or state variables, while also providing a significant speedup compared to DIDP (Kuroiwa and Beck 2025b). A RPID model uses three interfaces (called traits in Rust) to describe a DP model: 1) Dp - () TargetState() defines the target state, () IsBaseState(S) determines when S is a base state with cost () BaseCost(S), and () GenSucc(S) generates a set of successors ⟦τ⟧S_ τ with transition weight wτ()w_τ(S), 2) Dominance - (,′) Dominates(S,S ) determines if S dominates ′S to prevent exploring redundant states and 3) Bound - () Dual(S) returns the dual bound. Using these functions, Equation (1) recursively defines the value V(S) of a state (for a minimisation problem) as the minimum value of the successor states and the transition weight, where Inequality (2) specifies the dominance relationship and Inequality (3) the dual bound. Thus, solving Equation (1) provides the optimal solution. V()=()if ()min(wτ(),⟦τ⟧)∈()wτ()+V(⟦τ⟧)else V(S)= cases BaseCost(S) 46.94687ptif IsBaseState(S)\\ _(w_τ(S),\ S_ τ )∈ GenSucc(S)w_τ(S)+V(S_ τ ) 2.84544ptelse cases (1) V()≤V(′)if (,′) V(S)≤ V(S ) ------------------if Dominates(S,S ) (2) V()≥() V(S)≥ Dual(S) (3) Heuristic Search Heuristic search is a strategy for solving problems, using a heuristic h()h(S) to influence which state to expand. In this work, we use two heuristic search algorithms implemented in RPID: A∗A^* (Hart et al. 1968) and Complete Anytime Beam Search (CABS) (Zhang 1998). In RPID, both A∗A^* and CABS use the dual bound as h()h(S) and the cost to a node g()g(S) to guide the search, expanding the node with the minimum f()=g()+h()f(S)=g(S)+h(S). However, as opposed to A∗A^*, CABS stores at most b states with minimum f()f(S) in each layer (storing at most (n×b)O(n× b) states at a time, where n is the branching factor), increasing b until termination. CABS has shown superior memory use and ability to prove optimality/infeasibility (Kuroiwa and Beck 2023b) while also providing intermediate solutions. Pseudocode for heuristic search in DIDP can be seen in Algorithm 1; it starts with the target state, (heuristically) selecting a state to expand, and generating its successors while avoiding dominated/redundant states, iterating this process until a termination condition is met. Algorithm 1 Simplified Heuristic Search in RPID ←(),ℰ←∅,Primal←∞O←\ TargetState()\,\ E← ,\ Primal←∞ while ¬() ShouldTerminate() do ←min∈f(),←∖S← _S f(S),\ O \S\ if () IsBaseState(S) then Primal←minPrimal,g()+()Primal← \Primal,g(S)+ BaseCost(S)\ continue for (wτ(),⟦τ⟧)∈()(w_τ(S),S_ τ )∈ GenSucc(S) do h(⟦τ⟧)←(⟦τ⟧)h(S_ τ )← Dual(S_ τ ) if f(⟦τ⟧)≤Primal∧∄′∈ℰf(S_ τ )≤ Primal \ s.t. (′,⟦τ⟧)∧g(′)≤g(⟦τ⟧) Dominates(S ,S_ τ )\ \ g(S )≤ g(S_ τ ) then ←(,⟦τ⟧),ℰ←ℰ∪⟦τ⟧O← Insert(O,S_ τ ),\ E ∪\S_ τ \ 2.2 Constraint Programming Constraint Programming (CP) is a paradigm for solving combinatorial problems in the form of a constraint satisfaction problem (CSP), represented by the tuple (,,)(X,C,D), where X is the set of variables, C is the set of constraints specifying the relations between variables, and D is the domain which maps x∈x to its possible values (x)⊆D(x) . The goal is to find a solution ℐI: a mapping of each variable x∈x to a value vx∈(x)v_x (x) which satisfies all constraints. A CSP can be transformed into a constraint optimisation problem (COP) by adding an objective function which maps a solution ℐI to a value: o:ℐ↦o . The goal is then to find a solution that minimises (or maximises) this value. One strength of CP solvers is the use of inference techniques, which prune values from the domains of variables that cannot be part of a feasible solution. Concretely, constraints are represented in the CP solver by one or more propagators. Thus, a propagator can be seen as a function p:↦′p such that ∀x∈:(x)⊇′(x)∀ x :D(x) (x), where a propagator is at fixed-point if p()=p(D)=D. We define (x) LB(x) ((x) UB(x)) as the minimum (maximum) value that can be assigned to x∈x in D. Importantly, propagators are applied independently, but multiple propagators can be used together to express complex relationships between variables. In this work, we use two constraints and corresponding propagation algorithms, which are implemented in CP solvers such as Pumpkin (Flippo et al. 2024), Huub (Dekker et al. 2025), and CP-SAT (Perron and Didier 2025): The Disjunctive constraint (Carlier 1982), states that a set of jobs should not overlap. Each job has a variable starting time and a (variable) duration. The most prevalent propagation algorithm is edge-finding (Vilím 2004), which reasons over whether scheduling a job i as early (late) as possible is not possible due to another set of jobs Ω to infer that i should be processed after (before) Ω . The Cumulative constraint (Aggoun and Beldiceanu 1992), states that the cumulative resource usage of a set of tasks should not exceed the capacity at any time point. Each task has a variable starting time, a duration, and resource usage. The most common propagation algorithm is time-table filtering (Beldiceanu and Carlsson 2002), which reasons about when tasks are guaranteed to consume resources to infer that another task cannot be processed at these times. 3 Related Work Combining constraint propagation with dynamic programming was discussed by Hooker and van Hoeve (2018), and while there has been work in this area, a generic approach for incorporating constraint propagation with heuristic search in a model-based way has remained elusive. Fontaine et al. (2023) apply propagation after each solution to tighten time windows when solving TSPTW using a variation of A∗A^* (Vadlamudi et al. 2012). Additionally, pruning techniques for DP approaches play a key role in reducing the search space for optimal decision tree problems (brița2025optimal). While these approaches apply propagation within DP, their approach, unlike ours, relies on problem-specific propagation in a non-model-based approach. Generic propagation in a DP approach has been applied by Tanaka and Fujikuma (2012), making use of the Disjunctive for the 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i problem. Their approach uses the Lagrangian relaxation to generate tight bounds based on a network representation, pruning states by propagating the Disjunctive constraint. However, as opposed to our work, they do not use a model-based approach, limiting the transferability of their techniques. From a CP perspective, the work by Chu et al. (2010) proposes automatic identification and exploitation of subproblem dominance/equivalence, which can be used to prune states in a CP solver. In a similar vein, Smith (2005) proposes to create a representation of a key based on the (reduced) CP domains for caching. In our work, rather than adjusting the CP solver by adding dominance/equivalence constraints, we take the natural definition of dominance/equivalence in a DP model and incorporate propagation into this framework rather than the other way around, which means that we are able to more easily integrate with heuristic search using dual bounds. Furthermore, the work of Perron (1999) transfers heuristic search to a CP solver. However, they do not leverage the dominance/duplication detection of the DP model. Lastly, Fox et al. (1989) proposed a model for problem solving by combining constraint satisfaction and heuristic search. However, the main difference between our work and theirs is that we perform constraint propagation for search in a generic model-based framework. 4 DIDP with Constraint Propagation We describe our framework for incorporating constraint propagation, and, for three problems, we describe the DP model and the incorporation of constraint propagation. 4.1 Framework There are many possible architectures for combining solvers. Part of this space has been explored by the development of hybridisations of CP with fields such as Linear Programming (Beck and Refalo 2003; Laborie and Rogerie 2016), Satisfiability (SAT) (Ohrimenko et al. 2009; Feydy and Stuckey 2009), and Mixed-Integer Programming (Hooker 2005). Additionally, there is extensive work on hybridisation architectures in the context of SAT Modulo Theories (Nieuwenhuis et al. 2006). In our initial effort to develop a generic hybridisation of DP and CP, we chose to develop the simplest interface that would allow a DP solver to exploit the main technology of CP: constraint propagation. Figure 1: An overview of the interactions in our framework. To this end, we utilise a generic CP solver implementing constraint propagation to provide information to the DP solver. An overview of the interactions between these two components can be seen in Figure 1. At its core, the CP solver provides two pieces of information: 1) when a state S is infeasible, i.e., dynamically adding state/transition preconditions, and 2) a dual bound () DualCP(S). It should be noted that this information can be determined by any approach (e.g., decision diagram solvers or linear programs). To improve usability, we do not modify the search, but replace () GenSucc(S) in Algorithm 1 with (,Primal) GenSuccPropagation(S,Primal) (Algorithm 2), and (⟦τ⟧) Dual(S_ τ ) with max(⟦τ⟧),(⟦τ⟧,′) \ Dual(S_ τ ), DualCP(S_ τ ,D )\. Algorithm 2 first creates the CP model, which is propagated to obtain ′D and checked for infeasibility using (,′) IsInfeasible(S,D ) and (,′) DualCP(S,D ); one benefit of using CP is that ′D can be used to strengthen the dual bound. Next, successor infeasibility is checked in (⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ); since ′D is valid for any successor ⟦τ⟧S_ τ , ′D is used in (⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ) to avoid propagation. In practice, we only initialise X and C for the target state, and adjust D to represent every state. Algorithm 2 (,Primal) GenSuccPropagation(S,Primal) (,,)←()(X,C,D)← CPModel(S) ′←(,,)D ← Propagate(X,C,D) if (,′)∨g()+(,′)≥Primal IsInfeasible(S,D ) \ g(S)+ DualCP(S,D )≥ Primal then return ∅ Successors←∅Successors← for (wτ(),⟦τ⟧)∈()(w_τ(S),S_ τ )∈ GenSucc(S) do if ¬(⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ) then Successors←Successors∪(wτ(),⟦τ⟧)Successors← Successors∪\(w_τ(S),S_ τ )\ return SuccessorsSuccessors 4.2 |,|∑ 1|r_i, _i|Σ w_iT_i The single-machine scheduling problem 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i is formulated as follows: given are n jobs =j0,⋯,jn−1J=\j_0,·s,j_n-1\ which need to be processed on a single machine without overlapping. Each job i∈i has a duration pi∈+p_i ^+, a release time ri∈r_i , a deadline di∈d_i , a weight wi∈w_i , and a latest possible finish time δi∈ _i . The goal is to assign a start time sis_i to each job such that ri≤si<si+pi≤δir_i≤ s_i<s_i+p_i≤ _i, minimising the weighted tardiness ∑i∈wiTi _i w_iT_i, where Ti=max0,si+pi−diT_i= \0,s_i+p_i-d_i\. DP Model The DP model (adapted from Abdul-Razaq et al. (1990)) schedules one job at a time. We track the unscheduled jobs U and current time t in =(,t)S=(U,t). Additionally, we define the next available time after scheduling i as t′(t,i)=maxt,ri+pit (t,i)= \t,\ r_i\+p_i, the set of unscheduled jobs for which the time-window is not violated when scheduled B=i∈:t′(t,i)≤δiB=\i :t (t,i)≤ _i\, and the successor state ⟦i⟧=(∖i,t′(t,i))S_ i =(U \i\,t (t,i)). The Bellman equation is then defined as: V(,t)=0if =∅∞if ≠Bmini∈wi×Ti+V(⟦i⟧)else V(U,t)= [0.0pt][l]$ cases0&if U= \\ ∞&if U≠ B\\ _i w_i× T_i+V(S_ i )&else cases$ (4) V(,ta)≤V(,tb) V(U,t^a)≤ V(U,t^b) if ta≤tb t^a≤ t^b (5) V(,t)≥∑i∈wi×max0,maxri,t+pi−diV(U,t)≥Σ _i w_i× \0, \r_i,t\+p_i-d_i\ (6) Equation (4) states that a state is infeasible if there are jobs that cannot be scheduled due to time windows. Inequality (5) states that state a dominates state b if state a schedules the same jobs as state b but does so in less time. Inequality (6) describes a dual bound as the sum of tardinesses if all unscheduled jobs were started at maxri,t \r_i,t\. Constraint Propagation The variables X and domains D created in () CPModel(S) are described in Definition (8); for each unscheduled job i, a CP variable for the start time is created, which starts after rir_i and all scheduled jobs. The CP constraints C are then defined by Constraint (7), which uses the Disjunctive to ensure that no jobs overlap. ([si|i∈],[pi|i∈]) Disjunctive([s_i\ |\ i ],[p_i\ |\ i ]) (7) si∈[maxri,t,δi−pi] s_i∈[ \r_i,\ t\,\ _i-p_i] ∀i∈ ∀ i (8) After (,,) Propagate(X,C,D), we use the reduced domains ′D in (,′) DualCP(S,D ) as shown in Inequality (9), which states a dual bound as the sum of tardinesses of all unscheduled jobs if started at (si) LB(s_i). Additionally, Equation (10) describes (⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ), where a successor is infeasible if τ cannot be scheduled at t′(t,τ)t (t,τ). V(,t)≥∑i∈wi×max0,(si)+pi−diV(U,t)≥\ Σ _i w_i× \0, LB(s_i)+p_i-d_i\ (9) V(⟦τ⟧)=∞ V(S_ τ )=∞ if t′(t,τ)∉′(sτ) t (t,τ) (s_τ) (10) 4.3 RCPSP The Resource Constrained Project Scheduling Problem can be formulated as follows: given are n tasks =t0,⋯,tn−1T=\t_0,·s,t_n-1\ which are to be scheduled on a set of resources ℛR where each resource r∈ℛr has a capacity Cr∈+C_r ^+. Each task has a duration pi∈+p_i ^+, and a resource usage uir∈u_ir per resource r∈ℛr . The goal is to assign a start time sis_i to each task such that 1) the cumulative resource usage never exceeds any resource capacity, and 2) a set of precedence constraints is respected, as shown in Inequalities (11)-(12) (where H=∑i∈piH= _i p_i). We define the predecessors of task i as PreiPre_i. The objective is to minimise the makespan: maxi∈si+pi _i s_i+p_i. ∑i∈:si≤t∧si+pi≥tuir≤Cr _i \ :\ s_i≤ t\ \ s_i+p_i≥ tu_ir≤ C_r ∀t∈[0,H],r∈ℛ ∀ t∈[0,H],\ r \ (11) si+pi≤sj s_i+p_i≤ s_j ∀(i,j)∈ ∀(i,j) (12) DP Model We introduce a DP model based on scheduling one task at a time. We keep track of the partial schedule PSPS mapping each scheduled task j to its scheduled start time PSjPS_j (and each unscheduled task to ⊥ ), and the current time t in =(PS,t)S=(PS,t). We define the set of scheduled tasks S=i|i∈:PSi≠⊥S=\i\ |\ i :PS_i≠ \ (and =∖SU=T S). Equation (13) defines t′(t,τ)t (t,τ) as the earliest time where 1) there is no resource conflict when scheduling τ and 2) all of the predecessors of τ have finished. We then define the successor state as ⟦τ⟧=((PS∖(τ,⊥))∪(τ,t′(t,τ),t′(t,τ))S_ τ =((PS \(τ, )\)∪\(τ,t (t,τ)\,t (t,τ)); we also define (PS,t)=maxmaxi∈SPSi+pi,maxi∈t+pi Makespan(PS,t)= \ _i∈ S\PS_i+p_i\, _i \t+p_i\\, and (,τ)=((⟦τ⟧,t′(t,τ))−(,t)) W(S,τ)=( Makespan(S_ τ ,t (t,τ))- Makespan(S,t)). t′(t,τ)=minh∈[t,H] s.t. ∄r∈ℛ:uτr+∑i∈S:si≤h∧si+pi>huir>Cr∧Preτ⊆j|j∈S∧sj+pj≤ht (t,τ)= cases h∈[t,H] s.t. r \ :\\ u_τ r+Σ _i∈ S\ :\ s_i≤ h\ \ s_i+p_i>hu_ir>C_r\\ \ Pre_τ \j\ |\ j∈ S s_j+p_j≤ h\ cases (13) The Bellman equation is then defined as: V(PS,t)=0if S=mini∈:Prei⊆S(,τ)+V(⟦τ⟧)if S≠ V(PS,t)= cases0&if S=T\\ _i :Pre_i S W(S,τ)+V(S_ τ )&if S cases (14) V(a)≤V(b)if Sa=Sb∧ta≤tb∧∀i∈S:max(PSja,PSjb)+pj>t→PSia≤PSib V(S^a)≤ V(S^b) casesS^a=S^b\ \ t^a≤ t^b\ \\ ∀ i∈ S: (PS^a_j,PS^b_j)\\ +p_j>t→ PS^a_i≤ PS^b_i cases (15) V(⟦τ⟧)≤V(⟦τ′⟧) V(S_ τ )≤ V(S_ τ ) if t′(t,τ)+pτ≤t′(t,τ′) t (t,τ)+p_τ≤ t (t,τ ) (16) V(PS,t)≥(CriticalPath(,)) V(PS,t)≥ Length(CriticalPath(P,U)) (17) V(PS,t)≥maxr∈ℛ⌈∑i∈uir×piCr⌉ V(PS,t)≥ _r _i u_ir× p_iC_r (18) Inequality (15) describes dominance between states a and b; if they have scheduled the same tasks but a has scheduled all tasks sooner than b, then a dominates b. Similarly, Inequality (16) describes a transition dominance using the left-shift rule (Demeulemeester and Herroelen 1992); if there are two transitions τ,τ′∈()τ,τ ∈ T(S), then ⟦τ⟧S_ τ dominates ⟦τ′⟧S_ τ if we can complete task τ before starting τ′τ . Inequality (17) states that V(S) is larger than the length of the longest path through the precedence graph (i.e., the critical path). Inequality (18) states an energy-based dual-bound. Constraint Propagation The variables X and domains D created in () CPModel(S) are described in Definitions (22)-(24); for each task i, a CP variable sis_i for the start time is created, and a CP variable o for the objective is created. The CP constraints C are defined as: Constraint (19) specifies the Cumulative which ensures the resource capacity is not exceeded (where St=[si|i∈]St=[s_i\ |\ i ], P=[pi|i∈]P=[p_i\ |\ i ], and Ur=[uir|i∈]U_r=[u_ir\ |\ i ]), Constraint (20) ensures that precedences hold, and Constraint (21) defines the makespan. (St,P,Ur,Cr) Cumulative(St,P,U_r,C_r) ∀r∈ℛ ∀ r (19) si+pi≤sj s_i+p_i≤ s_j ∀(i,j)∈ ∀(i,j) (20) si+pi≤o≤Primal s_i+p_i≤ o≤ Primal ∀i∈ ∀ i (21) sj=PSj s_j=PS_j ∀j∈S ∀ j∈ S (22) si∈[t,H−pi] s_i∈[t,H-p_i] ∀i∈ ∀ i (23) o∈[0,H] o∈[0,H] (24) After (,,) Propagate(X,C,D), we use the bounds ′D in (,′) DualCP(S,D ) as described in 1) Inequality (25), which specifies a lower-bound on the makespan based on the earliest completion time (Vilím 2009), and 2) Inequality (26), which states that the makespan of a state is at least as large as the maximum latest finish time of the unscheduled tasks. Additionally, Equation (27) describes (⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ), where a successor is not feasible if task τ cannot be scheduled at time t′(t,τ)t (t,τ). V()≥maxr∈ℛmaxΩ⊆⌈Crmini∈Ω(si)+∑i∈Ω(uir×pi)Cr⌉V(S)≥ _r _ \ C_r _i∈ LB(s_i)+Σ _i∈ (u_ir× p_i)C_r \ (25) V(PS,t)≥maxi∈(si)+piV(PS,t)≥ _i \ LB(s_i)+p_i\ (26) V(⟦τ⟧)=∞ V(S_ τ )=∞ if t′(t,τ)∉′(sτ) t (t,τ) (s_τ) (27) 4.4 TSPTW The Travelling Salesperson Problem with Time Windows can be formulated as follows: given are n locations =l0,⋯,ln−1C=\l_0,·s,l_n-1\ which need to be visited, with a travel time cij∈c_ij between locations i and j. Each location i needs to be visited within [ri,δi][r_i, _i]; if the salesperson arrives at location i before rir_i then they wait until time rir_i. We define cij∗c_ij^* as the shortest travel time between location i and j. The goal is to determine the order in which to visit the locations, starting and ending at the depot l0l_0 while visiting each location besides the depot exactly once, such that the total travel time is minimised (excluding waiting times). DP Model The DP model (Kuroiwa and Beck 2023b) is based on visiting one location at a time. We track the unvisited locations U, current location l, and current time t in =(,l,t)S=(U,l,t). Additionally, we define t′(i,j)=maxt+cij,rjt (i,j)= \t+c_ij,r_j\, ⟦j⟧=(∖j,j,t′(l,j))S_ j =(U \j\,j,t (l,j)), O=j|j∈:t+cij∗>δjO=\j\ |\ j \ :\ t+c_ij^*> _j\, (l)=mini∈:i≠jcil MinTo(l)= _i :i≠ jc_il, (l)=mini∈:i≠jcli MinFrom(l)= _i :i≠ jc_li, and Ri=j∈|t+cij≤δjR_i=\j \ |\ t+c_ij≤ _j\. The Bellman equation is then defined as: V()=∞if O≠∅ci0if =∅minj∈Rlclj+V(⟦j⟧)else V(S)= [0.0pt][l]$ cases∞&if O≠ \\ c_i0&if U= \\ _j∈ R_lc_lj+V(S_ j )&else cases$ (28) V(,l,ta)≤V(,l,tb) V(U,l,t_a)≤ V(U,l,t_b) if ta≤tb t_a≤ t_b (29) V(,l,t)≥(l0)+∑i∈(i)(l)+∑i∈(i) V(U,l,t)≥ [0.0pt][l]$ cases MinTo(l_0)+ _i MinTo(i)\\ MinFrom(l)+ _i MinFrom(i) cases$ (30) Inequality (29) states that state a dominates state b if 1) they have visited the same locations, 2) are at the same current location, and 3) the current time of state a is earlier than the current time of state b. Inequality (30) uses the minimum travel time to an unvisited location i from another location and the minimum travel time from an unvisited location i to another location to calculate a dual bound on S. Constraint Propagation The variables X and domains D created in () CPModel(S) are described in Definitions (33)-(35); for each unvisited location i, a CP variable sis_i for the arrival time and time to next location pip_i is created, where the bounds on pip_i can be tightened if ∃j∈∖i:(sj)≥(si)∃ j \i\: LB(s_j)≥ UB(s_i), signifying that the depot cannot be visited from i. Additionally, a CP variable o for the objective is created. The constraints C, a relaxation of TSPTW, are defined as 1) Constraint (31) stating that no locations can be visited simultaneously, and 2) Constraint (32) defining the objective. ([si|i∈∪l],[pi|i∈∪l]) Disjunctive([s_i\ |\ i ∪\l\],[p_i\ |\ i ∪\l\]) (31) o=∑i∈pi≤Primal o=Σ _i p_i≤ Primal (32) si∈[maxt,ri,δi] s_i∈[ \t,r_i\, _i] ∀i∈∪l ∀ i ∪\l\ (33) pi∈cij|j∈(∪l0)∖i∧cij≠∞ p_i∈\c_ij|j∈(U∪\l_0\) \i\ c_ij≠∞\ ∀i∈∪l ∀ i ∪\l\ (34) o∈[0,maxi∈δi+ci0] o∈[0, _i _i+c_i0] (35) After (,,) Propagate(X,C,D), we use the bounds ′D in (,′) DualCP(S,D ) as described in Inequality (36), which states that a dual bound is the sum of the lower bounds of the travel times inferred by constraint propagation. Additionally, Equation (37) describes (⟦τ⟧,′) IsSuccInfeasible(S_ τ ,D ), where visiting τ next is infeasible if its arrival time or the travel time from the previous location is not possible. V(,l,t)≥∑i∈∪l(pi)V(U,l,t)≥Σ _i ∪l LB(p_i) (36) V(⟦τ⟧)=∞ V(S_ τ )=∞ if t′(l,τ)∉′(sτ)∨clτ∉′(pτ) t (l,τ) (s_τ) c_lτ (p_τ) (37) 5 Experimentation Our aim is to empirically show the impact of constraint propagation on the number of state expansions and runtime when integrated with a DP solver. For all three problems, we show that constraint propagation reduces the search space. For 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i and TSPTW, we show that it is especially effective for tightly constrained instances. 5.1 Experimentation Setup The experiments are run single threaded on an Intel Xeon Gold 6248R 24C 3.0GHz processor (Centre 2024) with a limit of 30 minutes and 16GB of memory. We use the following benchmarks: • |,|∑ 1|r_i, _i|Σ w_iT_i - We generate 900 instances according to Davari et al. (2016). The instances contain 50 jobs with duration pi∈[1,10]p_i∈[1,10], release date ri∈[0,τP]r_i∈[0,τ P] (where P is the sum of durations), deadline di∈[ri+pi,ri+pi+ρP]d_i∈[r_i+p_i,r_i+p_i+ρ P], latest finish time δi∈[di,di+ϕP] _i∈[d_i,d_i+φ P], and weight wi∈[1,10]w_i∈[1,10]. We generate 10 instances for each combination of τ∈0,0.2,0.4,0.6,0.8,1τ∈\0,0.2,0.4,0.6,0.8,1\, ρ∈0.05,0.25,0.5ρ∈\0.05,0.25,0.5\, ϕ∈0.9,1.05,1.2,1.35,1.5φ∈\0.9,1.05,1.2,1.35,1.5\. • RCPSP - We make use of the 480 J90 instances from PSPLIB (Kolisch and Sprecher 1997). • TSPTW - We consider instances used by López-Ibáñez et al. (2013), excluding too easy/difficult sets or with fractional distances; resulting in 130 instances by Gendreau et al. (1998) and 50 instances by Ascheuer (1996). We use Pumpkin (Flippo et al. 2024) for propagation, and CABS and A∗A^* of RPID 0.3.1 as the search for the DP-based approaches. The code and models are available in the provided supplements. We evaluate the following approaches: • A∗A^*/CABS - The RPID model using A∗A^* or CABS. • A∗A^*/CABS+CP - The RPID model using A∗A^* or CABS with constraint propagation; the propagators are executed once per state. We also considered fixed-point propagation, but the computational cost was too high to be able to compete with other methods. • ORT - Uses MiniZinc 2.9.2 with OR-Tools CP-SAT 9.12 as solver (using free search, causing the solver to make use of a portfolio approach); included in the comparison as a reference state-of-the-art constraint-based solver. The CP models can be found in Appendix B. Experimentation Summary Overall, constraint propagation significantly prunes the search space for all problems. For 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i, RCPSP, and tightly constrained TSPTW problems, our approach solves more instances than the DP approach while using considerably fewer states. The runtime performance indicates that further work on reducing propagation time is warranted. 5.2 |,|∑ 1|r_i, _i|Σ w_iT_i Starting with 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i, Figure 2(a) shows that our approach solves significantly more instances using fewer states than the baseline versions, exhibiting the effectiveness of constraint propagation. This effectiveness is confirmed by Appendix A.1, which shows that our approach guides the search to better solutions in fewer expansions. While A∗A^*+CP initially solves more instances, it plateaus sooner than CABS+CP, ultimately solving fewer instances. Looking at the number of instances solved over time, Figure 2(b) shows that the best performing approach is CABS+CP, which proves optimality for three more instances and infeasibility (at the target state) on thirteen more than CABS. Interestingly, CABS+CP only overtakes CABS in the number of instances solved after 500 seconds, showing the impact of propagation overhead. Moreover, the lack of instances solved by OR-Tools indicates that it is our combination of DP with propagation that works well. (a) 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances solved compared to state expansions. Our approach is able to solve the most instances per expansion. (b) 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances solved compared to time. Our approach solves the most instances. Figure 2: Number of 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances solved compared to the number of state expansions and time. Parameter Analysis An overview of the number of instances solved across values of ϕφ (where a lower value means that the instances have tighter latest finish times), can be seen in Figure 3. It shows that CABS+CP outperforms CABS on constrained instances where ϕφ is small(er), indicating that the constraint propagation prunes well when instances are tightly constrained. Furthermore, it can be observed that the number of solved instances decreases as ϕφ increases for all approaches, but the rate of decrease differs. Specifically, when ϕ≤1.05φ≤ 1.05, CABS+CP outperforms CABS in terms of instances proven infeasible and optimal, but for instances where ϕ≥1.2φ≥ 1.2, CABS is equal to or outperforms CABS+CP. Figure 3: Number of 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances solved over ϕφ. The marked parts are instances proven infeasible and unmarked parts are instances proven optimal. Our approach solves the most instances when they are tightly constrained. 5.3 RCPSP Considering RCPSP, Figure 4(a) shows that constraint propagation increases the number of instances solved per state expansion considerably for CABS, exhibiting that constraint propagation is crucial when using a state-based approach for RCPSP. Appendix A.2 indicates that constraint propagation provides the most benefit when proving optimality. Additionally, Figure 4(b) shows that adding constraint propagation to CABS also increases the number of instances solved per second compared to CABS alone. As expected, since A∗A^*(+CP) rarely finds primal bounds, which are key for pruning, it falls behind CABS(+CP). OR-Tools is the best-performing solver of all, possibly due to using a depth-first backtracking search, which is well-suited for the problem. Nonetheless, A∗A^*/CABS+CP provide better primal and/or dual bounds than OR-Tools on numerous instances (as shown in Figure 11 of Appendix A.2). (a) RCPSP instances solved compared to state expansions. Our approach solves significantly more instances per state expansion. (b) RCPSP instances solved compared to time; our approach outperforms the DP baseline, but the best-performing approach is CP. Figure 4: Number of RCPSP instances solved compared to the number of state expansions and time. 5.4 TSPTW Turning to TSPTW, Figure 5(a) shows that constraint propagation decreases the number of solved instances due to a lack of pruning. This observation is demonstrated in the number of solved instances per state expansion of both A∗A^*/A∗A^*+CP and CABS/CABS+CP overlapping, likely due to instances being too loosely constrained to make inferences. This observation is further corroborated by Appendix A.3. This effect is also reflected by the number of instances solved over time in Figure 5(b), which shows that adding constraint propagation results in an increase in solving time. However, the worst-performing approach is OR-Tools. (a) TSPTW instances solved compared to state expansions. Our approach expands slightly fewer states than the DP approach. (b) TSPTW instances solved compared to time. The DP approach solves the most instances. Figure 5: Number of TSPTW instances solved compared to the number of state expansions and time. Parameter Analysis To determine the impact of instance constrainedness, we investigate parameterised instances (not part of the previous set) introduced by Rifki and Solnon (2025) where n=31n=31. For these instances, a low α indicates that many locations need to be visited relative to the horizon, while a low β means that time windows are tight. We consider two sets: 1) a general set of 135 instances where we select three instances per combination of α∈1.0,1.5,2,2.5,3α∈\1.0,1.5,2,2.5,3\ and β∈0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1β∈\0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1\, and 2) a set of 540 instances where we select ten instances per combination of α∈1.0,1.1,1.2,1.3,1.4,1.5α∈\1.0,1.1,1.2,1.3,1.4,1.5\ and the same values of β. Figure 6, shows that for α<1.2α<1.2, CABS+CP outperforms all other approaches. Examining Figure 7, shows that, when 1.0≤α≤1.51.0≤α≤ 1.5, the number of instances solved per state expansion is significantly increased compared to Figure 5(a). This effect can be explained by CABS+CP reducing the number of states by orders of magnitude compared to CABS (Figure 8), where especially infeasible instances benefit from constraint propagation. Overall, the DP-based methods solve fewer instances as α increases, but the rate of decrease differs, causing CABS to outperform CABS+CP when α≥1.2α≥ 1.2. Interestingly, OR-Tools proves optimality on the most instances, likely due to 1) lower memory usage, and 2) stronger propagation (using Circuit (Laurière 1978)). Figure 6: Number of solved TSPTW Rifki and Solnon (2025) instances across values of α. The marked parts are instances proven infeasible and unmarked parts are instances proven optimal. The lower plot uses an extended set of instances to show 1.0≤α≤1.51.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.51.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.51.0≤α≤ 1.5). Our approach reduces the number of expansions by orders of magnitude. 6 Conclusions and Future Work We have presented a framework that integrates constraint propagation into a DP solver, and implemented it in the modelling of DIDP. Our approach allows us to combine the strengths of heuristic guidance and dominance/duplicate detection of DP with the inference techniques of CP. Our evaluation on three combinatorial optimisation problems shows that adding constraint propagation significantly increases the number of instances solved per state expansion, solving more instances than a DP solver alone for 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i, RCPSP, and tightly constrained TSPTW instances. As to runtime, the benefit of propagation outweighs the cost for tightly constrained instances, but further work into reducing propagation time could improve performance further. In our in-depth analysis, we vary 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i and TSPTW instance constrainedness, which shows that propagation performs exceptionally well when instances are highly constrained. Our work is a key step in understanding the value of constraint propagation in DP solvers, providing a model-based way of integrating DP and CP. Our interface is generic, allowing future work to investigate the integration of DP solvers with other techniques besides CP. Another strength of our framework is the simplicity of the interface; similar to SAT Modulo Theories architecture, the interface could be enriched to investigate the impact of additional information on the DP solver. Another direction is to explore what is represented in the CP model, e.g., the DP model could be a relaxation, while the CP model contains the absent elements of the DP model. Finally, future work could look into reducing propagation overhead, e.g., by reducing redundant work introduced by jumping between states, or by determining when to propagate. Acknowledgements Imko Marijnissen is supported by the NWO/OCW, as part of the Quantum Software Consortium programme (project number 024.003.037 / 3368). References T.S. Abdul-Razaq, C.N. Potts, and L.N. Van Wassenhove (1990) A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Applied Mathematics 26 (2), p. 235–253. External Links: ISSN 0166-218X, Document, Link Cited by: §4.2. A. Aggoun and N. Beldiceanu (1992) Extending CHIP in order to solve complex scheduling and placement problems. In JFPL’92, 1ères \`eres Journées Francophones de Programmation Logique, 25-27 Mai 1992, Lille, France, J. Delahaye, P. Devienne, P. Mathieu, and P. Yim (Eds.), p. 51. Cited by: §2.2. N. Ascheuer (1996) Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. Ph.D. Thesis, Konrad-Zuse-Zentrum für Informationstechnik Berlin, (en). Cited by: 3rd item. J. C. Beck and P. Refalo (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118 (1-4), p. 49–71. External Links: Link, Document Cited by: §4.1. N. Beldiceanu and M. Carlsson (2002) A new multi-resource cumulatives constraint with negative heights. In Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, P. V. Hentenryck (Ed.), Lecture Notes in Computer Science, Vol. 2470, p. 63–79. External Links: Link, Document Cited by: §2.2. D. Bergman, A. A. Ciré, W. van Hoeve, and J. N. Hooker (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28 (1), p. 47–66. External Links: Link, Document Cited by: §1. J. Carlier (1982) The one-machine sequencing problem. European Journal of Operational Research 11 (1), p. 42–47. Note: Third EURO IV Special Issue External Links: ISSN 0377-2217, Document, Link Cited by: §2.2. D. H. P. C. Centre (2024) DelftBlue Supercomputer (Phase 2). Note: https://w.tudelft.nl/dhpc/ark:/44463/DelftBluePhase2 Cited by: §5.1. G. Chu, M. G. de la Banda, and P. J. Stuckey (2010) Automatically exploiting subproblem equivalence in constraint programming. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, 2010. Proceedings, A. Lodi, M. Milano, and P. Toth (Eds.), Lecture Notes in Computer Science, Vol. 6140, p. 71–86. External Links: Link, Document Cited by: §1, §3. G. Chu and P. J. Stuckey (2015) Dominance breaking constraints. Constraints An Int. J. 20 (2), p. 155–182. External Links: Link, Document Cited by: §1. M. Davari, E. Demeulemeester, R. Leus, and F. T. Nobibon (2016) Exact algorithms for single-machine scheduling with time windows and precedence constraints. J. Sched. 19 (3), p. 309–334. External Links: Link, Document Cited by: 1st item. J. J. Dekker, A. Ignatiev, P. J. Stuckey, and A. Z. Zhong (2025) Towards Modern and Modular SAT for LCG. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), M. G. de la Banda (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 340, Dagstuhl, Germany, p. 42:1–42:12. Note: Keywords: Lazy Clause Generation, Boolean Satisfiability, IPASIR-UP External Links: ISBN 978-3-95977-380-5, ISSN 1868-8969, Link, Document Cited by: §2.2. E. Demeulemeester and W. Herroelen (1992) A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science 38 (12), p. 1803–1818. External Links: ISSN 00251909, 15265501, Link Cited by: §4.3. T. Feydy and P. J. Stuckey (2009) Lazy clause generation reengineered. In Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, September 20-24, 2009, Proceedings, I. P. Gent (Ed.), Lecture Notes in Computer Science, Vol. 5732, p. 352–366. External Links: Link, Document Cited by: §4.1. M. Flippo, K. Sidorov, I. Marijnissen, J. Smits, and E. Demirović (2024) A Multi-Stage Proof Logging Framework to Certify the Correctness of CP Solvers. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024), P. Shaw (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 307, Dagstuhl, Germany, p. 11:1–11:20. Note: Keywords: proof logging, formal verification, constraint programming External Links: ISBN 978-3-95977-336-2, ISSN 1868-8969, Link, Document Cited by: §2.2, §5.1. R. Fontaine, J. Dibangoye, and C. Solnon (2023) Exact and anytime approach for solving the time dependent traveling salesman problem with time windows. Eur. J. Oper. Res. 311 (3), p. 833–844. External Links: Link, Document Cited by: §1, §3. M. S. Fox, N. M. Sadeh, and C. A. Baykan (1989) Constrained heuristic search. In Proceedings of the 11th International Joint Conference on Artificial Intelligence. Detroit, MI, USA, August 1989, N. S. Sridharan (Ed.), p. 309–315. External Links: Link Cited by: §3. M. Gendreau, A. Hertz, G. Laporte, and M. Stan (1998) A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. 46 (3), p. 330–335. External Links: Link, Document Cited by: 3rd item. X. Gillard, P. Schaus, and V. Coppé (2020) Ddo, a generic and efficient framework for mdd-based optimization. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, C. Bessiere (Ed.), p. 5243–5245. External Links: Link, Document Cited by: §1. P. E. Hart, N. J. Nilsson, and B. Raphael (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4 (2), p. 100–107. External Links: Link, Document Cited by: §2.1. J. N. Hooker and W. J. van Hoeve (2018) Constraint programming and operations research. Constraints An Int. J. 23 (2), p. 172–195. External Links: Link, Document Cited by: §3. J. N. Hooker (2005) A hybrid method for the planning and scheduling. Constraints An Int. J. 10 (4), p. 385–401. External Links: Link, Document Cited by: §4.1. R. Kolisch and A. Sprecher (1997) PSPLIB - a project scheduling problem library: or software - orsep operations research software exchange program. European Journal of Operational Research 96 (1), p. 205–216. External Links: ISSN 0377-2217, Document, Link Cited by: 2nd item. R. Kuroiwa and J. C. Beck (2023a) Domain-independent dynamic programming: generic state space search for combinatorial optimization. In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling, Prague, Czech Republic, July 8-13, 2023, S. Koenig, R. Stern, and M. Vallati (Eds.), p. 236–244. External Links: Link, Document Cited by: §1. R. Kuroiwa and J. C. Beck (2023b) Solving domain-independent dynamic programming problems with anytime heuristic search. Proceedings of the International Conference on Automated Planning and Scheduling 33 (1), p. 245–253. External Links: Link, Document Cited by: §2.1, §2.1, §4.4. R. Kuroiwa and J. C. Beck (2025a) Domain-independent dynamic programming. External Links: 2401.13883, Link Cited by: §1. R. Kuroiwa and J. C. Beck (2025b) RPID: rust programmable interface for domain-independent dynamic programming. In 31st International Conference on Principles and Practice of Constraint Programming, CP 2025, August 10-15, 2025, Glasgow, Scotland, M. G. de la Banda (Ed.), LIPIcs, Vol. 340, p. 23:1–23:21. External Links: Link, Document Cited by: §2.1. P. Laborie and J. Rogerie (2016) Temporal linear relaxation in IBM ILOG CP optimizer. J. Sched. 19 (4), p. 391–400. External Links: Link, Document Cited by: §4.1. J. Laurière (1978) A language and a program for stating and solving combinatorial problems. Artif. Intell. 10 (1), p. 29–127. External Links: Link, Document Cited by: §5.4. M. López-Ibáñez, C. Blum, J. W. Ohlmann, and B. W. Thomas (2013) The travelling salesman problem with time windows: adapting algorithms from travel-time to makespan optimization. Appl. Soft Comput. 13 (9), p. 3806–3815. External Links: Link, Document Cited by: 3rd item. L. Michel and W. van Hoeve (2024) CODD: A decision diagram-based solver for combinatorial optimization. In ECAI 2024 - 27th European Conference on Artificial Intelligence, 19-24 October 2024, Santiago de Compostela, Spain - Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024), U. Endriss, F. S. Melo, K. Bach, A. J. B. Diz, J. M. Alonso-Moral, S. Barro, and F. Heintz (Eds.), Frontiers in Artificial Intelligence and Applications, Vol. 392, p. 4240–4247. External Links: Link, Document Cited by: §1. N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, and G. Tack (2007) MiniZinc: towards a standard CP modelling language. In Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, C. Bessiere (Ed.), Lecture Notes in Computer Science, Vol. 4741, p. 529–543. External Links: Link, Document Cited by: §1. R. Nieuwenhuis, A. Oliveras, and C. Tinelli (2006) Solving SAT and SAT modulo theories: from an abstract davis–putnam–logemann–loveland procedure to dpll(T). J. ACM 53 (6), p. 937–977. External Links: Link, Document Cited by: §4.1. O. Ohrimenko, P. J. Stuckey, and M. Codish (2009) Propagation via lazy clause generation. Constraints An Int. J. 14 (3), p. 357–391. External Links: Link, Document Cited by: §4.1. L. Perron and F. Didier (2025) CP-sat. Google. External Links: Link Cited by: §2.2. L. Perron (1999) Search procedures and parallelism in constraint programming. In Principles and Practice of Constraint Programming - CP’99, 5th International Conference, Alexandria, Virginia, USA, October 11-14, 1999, Proceedings, J. Jaffar (Ed.), Lecture Notes in Computer Science, Vol. 1713, p. 346–360. External Links: Link, Document Cited by: §3. O. Rifki and C. Solnon (2025) On the phase transition of the euclidean travelling salesman problem with time windows. J. Artif. Intell. Res. 82, p. 2167–2188. External Links: Link, Document Cited by: Figure 13, 13(a), 13(b), Figure 6, Figure 7, Figure 8, §5.4. B. M. Smith (2005) Caching search states in permutation problems. In Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, P. van Beek (Ed.), Lecture Notes in Computer Science, Vol. 3709, p. 637–651. External Links: Link, Document Cited by: §1, §3. P. J. Stuckey, T. Feydy, A. Schutt, G. Tack, and J. Fischer (2014) The minizinc challenge 2008-2013. AI Mag. 35 (2), p. 55–60. External Links: Link, Document Cited by: §1. S. Tanaka and S. Fujikuma (2012) A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. J. Sched. 15 (3), p. 347–361. External Links: Link, Document Cited by: §1, §3. S. G. Vadlamudi, P. Gaurav, S. Aine, and P. P. Chakrabarti (2012) Anytime column search. In AI 2012: Advances in Artificial Intelligence - 25th Australasian Joint Conference, Sydney, Australia, December 4-7, 2012. Proceedings, M. Thielscher and D. Zhang (Eds.), Lecture Notes in Computer Science, Vol. 7691, p. 254–265. External Links: Link, Document Cited by: §3. P. Vilím (2004) O(n log n) filtering algorithms for unary resource constraint. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, First International Conference, CPAIOR 2004, Nice, France, April 20-22, 2004, Proceedings, J. Régin and M. Rueher (Eds.), Lecture Notes in Computer Science, Vol. 3011, p. 335–347. External Links: Link, Document Cited by: §2.2. P. Vilím (2009) Edge finding filtering algorithm for discrete cumulative resources in O(knlogn) O( knlog n). In Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, September 20-24, 2009, Proceedings, I. P. Gent (Ed.), Lecture Notes in Computer Science, Vol. 5732, p. 802–816. External Links: Link, Document Cited by: §4.3. W. Zhang (1998) Complete anytime beam search. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30, 1998, Madison, Wisconsin, USA, J. Mostow and C. Rich (Eds.), p. 425–430. External Links: Link Cited by: §2.1. Appendices Appendix A Optimality Gap Analysis We discuss the impact of adding constraint propagation on the average optimality gap. For a minimisation problem, given a lower-bound DualDual and an upper-bound PrimalPrimal on the objective, Equation (38) defines the optimality gap. The optimality gap provides information about how far the lower- and upper-bound are from each other, the closer, the better. OptimalityGap=Primal−Dualmax1,PrimalOptimalityGap= Primal-Dual \1,Primal\ (38) We calculate the average optimality gap by starting with 1.01.0 for every instance for which infeasibility was not proven, and then updating the optimality gap for an instance whenever a new dual or primal bound is found, taking the average of all instances as the average optimality gap. We do not plot A∗A^* since it does not find intermediate solutions. A.1 |,|∑ 1|r_i, _i|Σ w_iT_i Figure 9(a) shows that, besides being able to solve more instances (as shown in Figure 2), our approach also reaches a better optimality gap in fewer states. This indicates that pruning also results in better bounds/solutions. Furthermore, Figure 9(b) shows that the optimality gap between CABS and CABS+CP over time is very similar. While our approach guides the search better and is able to solve more instances, the overhead of propagation causes a similarity in the optimality gap between the two approaches. (a) Average optimality gap over number of state expansions for 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances. Our approach achieves a smaller optimality gap using fewer states compared to CABS. (b) Average optimality gap over time for 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances. Our approach achieves a better optimality gap than CABS. Figure 9: Average optimality gap over the number of state expansions and time for 1|ri,δi|∑wiTi1|r_i, _i|Σ w_iT_i instances. A.2 RCPSP For RCPSP, Figure 10(a) shows that CABS(+CP) quickly approach an optimality gap of zero, indicating that it is the proving of optimality which is difficult for the approaches. Nevertheless, in addition to our approach substantially increasing the number of solved instances (Figure 4), our approach also reduces the optimality gap compared to CABS. These results further exhibit the importance of constraint propagation for DP-based approaches when solving RCPSP. Looking at the optimality gap over time, Figure 10(b) shows a similar trend to Figure 10(a), exhibiting that the optimality gap is also reduced over time by the addition of constraint propagation. Interestingly, both CABS and CABS+CP achieve a lower optimality gap than OR-Tools, showing the value of DP-based approaches for RCPSP. (a) Average optimality gap over number of state expansions for RCPSP. Our approach achieves a slightly better optimality gap than CABS, indicating that proving optimality is the difficulty. (b) Average optimality gap over time for RCPSP instances. Our approach achieves a better optimality gap than CABS and OR-Tools. Figure 10: Average optimality gap over the number of state expansions and time for RCPSP instances. This conclusion is further strengthened by Figure 11, which shows that, for numerous instances, our approach outperforms OR-Tools in terms of optimality gap. Figure 11: Comparison of optimality gap on RCPSP instances. Our approach improves the optimality gap of OR-Tools for numerous instances. A.3 TSPTW Similar to the conclusions of Section 5.4, Figure 12(a) shows that adding constraint propagation does not improve the optimality gap for the general instances. Since our approach times out for many instances, it reaches a higher optimality gap than CABS. The effect of propagation overhead with weak pruning can also be seen in Figure 12(b), showing that the propagation causes a slower convergence. Parameter Analysis Looking at the tightly constrained instances from Section 5.4, Figure 13(a) shows that our approach reaches a similar optimality gap as CABS, confirming the findings of Figure 8 that our approach mostly reduces the number of states on infeasible instances (which are not shown in these plots). Similar to Appendix A.1, Figure 13(b) indicates that future work into reducing the propagation overhead is warranted. Interestingly, while OR-Tools solves the most instances to optimality, it does not reach the lowest optimality gap. (a) Average optimality gap over number of state expansions for TSPTW instances. Our approach does not improve the optimality gap and times out with fewer state expansions than CABS. (b) Average optimality gap over time. Our approach does not improve the optimality gap compared to CABS for TSPTW instances. Figure 12: Average optimality gap over the number of state expansions and time for TSPTW instances. (a) Average optimality gap over number of state expansions for TSPTW instances by Rifki and Solnon (2025) where 1.0≤α≤1.51.0≤α≤ 1.5. Our approach achieves the same optimality gap as CABS. (b) Average optimality gap over time for TSPTW instances by Rifki and Solnon (2025) where 1.0≤α≤1.51.0≤α≤ 1.5. CABS reaches the lowest optimality gap, closely followed by our approach. 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.51.0≤α≤ 1.5. Appendix B CP Models We describe the models used for OR-Tools in the experiments. The MiniZinc models can be found in the provided experimental data. B.1 |,|∑ 1|r_i, _i|Σ w_iT_i The model defines the variable sis_i for the start time of job i in Definition (41). Constraint (40) ensures that the tasks do not overlap. Finally, the objective function (Objective (39)) specifies that the sum of weighted tardinesses is minimised. min∑i∈max0,si+pi−di×wi _i \0,s_i+p_i-d_i\× w_i (39) ([si|i∈],[pi|i∈]) Disjunctive([s_i\ |\ i ],[p_i\ |\ i ]) (40) si∈[ri,δi−pi] s_i∈[r_i, _i-p_i] ∀i∈ ∀ i (41) B.2 RCPSP The model is adapted from the MiniZinc benchmarks repository. The model defines two variables: sis_i for the start time of task i (Definition (46)) and the objective variable o (Definition (47)) representing the makespan. The constraints then consist of 1) Constraint (43), constraining the makespan to be after all of the variables (where sucisuc_i are the successors of task i according to the precedences), 2) Constraint (44), constraining the precedences to be respected, and 3) Constraint (45), ensuring that the resource capacities are respected (where r=i|i∈:uir>0∧pi>0T_r=\i\ |\ i :u_ir>0 p_i>0\, Str=[si|i∈r]St_r=[s_i\ |\ i _r], Pr=[pi|i∈r]P_r=[p_i\ |\ i _r], and Ur=[uir|i∈r]U_r=[u_ir\ |\ i _r]). Finally, the objective function (Objective (42)) specifies that the makespan variable is minimised. mino o (42) si+pi≤o s_i+p_i≤ o ∀i∈:suci≠∅ ∀ i :suc_i≠ (43) si+pi≤sj s_i+p_i≤ s_j ∀(i,j)∈ ∀(i,j) (44) (Str,Pr,Ur,Cr) Cumulative(St_r,P_r,U_r,C_r) ∀r∈ℛ ∀ r (45) si∈[0,H] s_i∈[0,H] ∀i∈ ∀ i (46) o∈[0,H] o∈[0,H] (47) B.3 TSPTW We adapt the model from the 2025 MiniZinc challenge. The model defines six variables: 1) Definition (55), which defines predipred_i, representing the predecessor for each location i (i.e. the location which was visited prior to this one), 2) Definition (56), which defines durToPredidurToPred_i, which represents the travel time from the predecessor of location i to i, 3) Definition (57), which defines arriarr_i, representing the arrival time at location i, 4) Definition (58), which defines depidep_i, representing the departure time at location i, 5) Definition (59), which defines depPredidepPred_i, representing the departure from the predecessor of location i, and 6) Definition (60), which defines the objective o, representing the sum of travel times. The following constraints are then specified: 1) Constraint (49) constrains o to be equal to the sum of travel times, 2) Constraint (50) constrains arriarr_i to be equal to the departure time at the predecessor of i plus the duration from the predecessor of i to i, 3) Constraint (51) ensures that durToPredidurToPred_i is equal to the travel time from the predecessor of location i to i, 4) Constraint (52) ensures that the latest possible visiting times are respected and that the departure at location i either occurs at its arrival or at its earliest possible release time, 5) Constraint (53) ensures that the depPredidepPred_i is properly channelled to be equal to the value of the variable depredidep_pred_i, and 6) Constraint (54) constrains the sequence of locations to be a tour using the Circuit constraint. Finally, the objective function (Objective (48)) specifies that the sum of travel times variable is minimised. mino o (48) o=∑i∈locationsdurToPredi o= _i∈ locationsdurToPred_i (49) arri=depPredi+durToPredi arr_i=depPred_i+durToPred_i ∀i∈ ∀ i (50) durToPredi=cpredii durToPred_i=c_pred_ii ∀i∈ ∀ i (51) depi=maxarri,ri≤δi dep_i= \arr_i,r_i\≤ _i ∀i∈ ∀ i (52) depPredi=depredi depPred_i=dep_pred_i ∀i∈ ∀ i (53) ([predi|∀i∈]) Circuit([pred_i\ |\ ∀ i ]) (54) predi∈[0,||] pred_i∈[0,|C|] ∀i∈ ∀ i (55) durToPred∈[0,maxi,j∈cij] durToPred∈[0, _i,j c_ij] ∀i∈ ∀ i (56) arri∈[0,maxi∈δi] arr_i∈[0, _i _i] ∀i∈ ∀ i (57) depi∈[mini∈ri,maxi∈δi] dep_i∈[ _i r_i, _i _i] ∀i∈ ∀ i (58) depPredi∈[0,maxi∈δi] depPred_i∈[0, _i _i] ∀i∈ ∀ i (59) o∈[0,||×maxi,j∈cij] o∈[0,|C|× _i,j c_ij] (60)