Domain-Independent Dynamic Programming with Constraint Propagation

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

Read Domain-Independent Dynamic Programming with Constraint Propagation by Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16648.txt.

Introduction

Marijnissen and co-authors merge dynamic programming with constraint propagation. Two solver styles dominate hard combinatorial problems. State-based search and constraint-based models rarely mix. Their solver prunes DP states and transitions using propagation. A general CP solver supplies the pruning inside the DIDP frame. Tests cover scheduling and routing problems with time windows. Propagation cut state expansions sharply. The combined solver beat a plain DP solver on two problem families.

Catalog record

CREATORImko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54958
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16648

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Domain-Independent Dynamic Programming with Constraint Propagation Imko Marijnissen, J. Christopher Beck, Emir Demirović, Ryo Kuroiwa 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 | r i , δ i | ∑ w i ​ T i 1|r_{i},\delta_{i}|\sum w_{i}T_{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 | r i , δ i | ∑ w i ​ T i 1|r_{i},\delta_{i}|\sum w_{i}T_{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 ( 25 ; 27 ) and MiniZinc ( 33 ; 40 ) 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 ( 6 ) , used by decision diagram solvers such as ddo ( 20 ) and CODD ( 32 ) . Previous works introduce constraint propagation in DP approaches, but they either only used problem-specific propagation ( 17 ; 7 ) , or did not use heuristic search ( 41 ) . Other, related but orthogonal, work has focused on using dominance and caching ( 11 ; 10 ; 39 ) 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|r_{i},\delta_{i}|\sum w_{i}T_{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|r_{i},\delta_{i}|\sum w_{i}T_{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|r_{i},\delta_{i}|\sum w_{i}T_{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 ( 26 ) . A DIDP model is a state-transition system where a solution is created by starting with a target state \mathcal{S}^{0} and applying a sequence of transitions until a base state is reached. A successor state \mathcal{S}_{\llbracket\tau\rrbracket} is created from \mathcal{S} by applying a possible transition \tau\in\mathrm{T}(\mathcal{S}) with weight w_{\tau}(\mathcal{S}) . The cost of a solution is the sum of transition weights plus the cost of the base state, where V ( \mathcal{S} ) maps \mathcal{S} to its optimal solution cost and the dual bound is a lower (upper) bound on V ( \mathcal{S} ) in minimisation (maximisation) problems. Thus, the goal of a DIDP solver is to compute V(\mathcal{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 ( 28 ) . A RPID model uses three interfaces (called traits in Rust) to describe a DP model: 1) Dp - \mathtt{TargetState}() defines the target state, \mathtt{IsBaseState}(\mathcal{S}) determines when \mathcal{S} is a base state with cost \mathtt{BaseCost}(\mathcal{S}) , and \mathtt{GenSucc}(\mathcal{S}) generates a set of successors \mathcal{S}_{\llbracket\tau\rrbracket} with transition weight w_{\tau}(\mathcal{S}) , 2) Dominance - \mathtt{Dominates}(\mathcal{S},\mathcal{S}^{\prime}) determines if \mathcal{S} dominates \mathcal{S}^{\prime} to prevent exploring redundant states and 3) Bound - \mathtt{Dual}(\mathcal{S}) returns the dual bound. Using these functions, Equation ( 1 ) recursively defines the value V ( \mathcal{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

Read the complete text