Domain-Independent Dynamic Programming with Constraint Propagation

This paper bridges the gap between dynamic programming and constraint programming by integrating constraint propagation into a domain-independent DP framework, demonstrating that this hybrid approach significantly reduces state expansions and improves the solving of constrained combinatorial optimization problems despite some runtime overhead.

The Gist

Imagine you are trying to solve a massive, incredibly complex puzzle. You have two main ways to tackle it:

1. The "Map Maker" Approach (Dynamic Programming): You draw a map of every possible path you could take. You start at the beginning and explore every route, but you have a smart rule: if you find a path that is clearly worse than one you've already seen, you cross it off your map. This is fast at finding the best route, but if the map is too huge, you run out of paper (memory) or time.
2. The "Rule Enforcer" Approach (Constraint Programming): You don't draw the whole map. Instead, you have a strict list of rules (e.g., "You can't be in two places at once," "You must arrive before 5 PM"). You use these rules to instantly realize that huge chunks of the puzzle are impossible, so you don't even bother looking at them.

The Problem:
For a long time, these two teams didn't talk to each other. The Map Makers were great at finding the best path but got overwhelmed by the sheer size of the map. The Rule Enforcers were great at cutting out impossible paths but sometimes got lost in the details of the rules without a clear strategy to find the best solution quickly.

The Solution: The "Super-Helper"
This paper introduces a new way to combine these two teams. The authors built a hybrid system where the Map Maker (the Dynamic Programming solver) has a "Super-Helper" (the Constraint Propagation engine) sitting right next to it.

Here is how it works, using a simple analogy:

The Analogy: Planning a Wedding Seating Chart

Imagine you are the wedding planner (the Map Maker). You are trying to figure out the perfect seating arrangement for 100 guests.

• Your Job: You try different combinations of who sits where. You keep a list of "good" arrangements you've found so far.
• The Problem: There are billions of combinations. If you try them one by one, you'll be working until the next century.

Enter the Super-Helper (The Constraint Propagator):
You hire a strict Auntie (the CP Solver) who knows all the family rules:

• "Uncle Bob and Aunt Sue can't sit together."
• "The bride's family must be on the left."
• "No one can sit next to the person they hate."

How they work together:

1. Before you even pick a seat: You ask Auntie, "If I put Uncle Bob here, is that possible?"
2. Auntie's Magic: She instantly looks at the rules and says, "No! If Bob is there, he clashes with three other people. Also, because of that, we can't put Cousin Tim in the back row, and we definitely can't put the Groom's brother at Table 4."
3. The Result: Instead of you trying to build a seating chart with Bob at that seat (and wasting hours realizing it fails later), Auntie tells you immediately that this entire branch of possibilities is dead. She "prunes" the bad branches before you even start walking down them.

What the Paper Actually Did

The researchers took this idea and applied it to three very hard real-world problems:

1. Scheduling Jobs on a Machine: Like a factory where machines have strict time windows.
2. Project Management: Like building a house where you need specific resources (cranes, workers) that can't be in two places at once.
3. The Traveling Salesperson: Like a delivery driver who must visit 50 cities within specific time windows.

They built a system where the "Map Maker" (the solver) asks the "Rule Enforcer" (the CP solver) for advice at every single step.

The Results: What Happened?

• For Tightly Constrained Problems (The "Hard" Puzzles): The system was a superstar. By letting the Rule Enforcer cut out impossible paths early, the Map Maker had to explore far fewer possibilities. It solved more problems than the Map Maker could do alone, and it did it faster.
  • Analogy: It's like having a GPS that tells you "This road is closed" before you even drive onto it, saving you hours of driving.
• For Loosely Constrained Problems (The "Easy" Puzzles): Sometimes, the Rule Enforcer spent too much time checking rules that didn't actually eliminate anything. In these cases, the extra time spent asking for advice slowed the system down slightly.
  • Analogy: If the road is wide open, asking a traffic cop "Can I drive here?" takes 5 seconds, but you could have just driven there in 1 second. The check was unnecessary.

The Big Takeaway

The paper proves that combining the "search strategy" of Dynamic Programming with the "rule-checking power" of Constraint Programming is a winning move, especially for difficult, tightly constrained problems.

It's like giving a chess grandmaster (the DP solver) a super-computer that instantly calculates all illegal moves (the CP solver). The grandmaster doesn't have to waste brainpower thinking about moves that break the rules; they can focus entirely on finding the winning strategy.

In short: They built a bridge between two different ways of solving puzzles, and on the hardest puzzles, that bridge made the solution much faster and more efficient.

Technical Summary

1. Problem Statement

The paper addresses a gap between two dominant paradigms in combinatorial optimization:

• State-based representations (Dynamic Programming - DP): These use heuristic search (e.g., A*, Beam Search) with dual bounds to explore state spaces. They excel at duplicate and dominance detection but often lack strong inference capabilities to prune infeasible paths early.
• Constraint-based representations (Constraint Programming - CP): These use depth-first search and inference (constraint propagation) to prune variable domains based on constraints. They excel at pruning but traditionally lack the specific dominance/duplicate detection mechanisms inherent to DP.

The Core Challenge: While previous works have integrated propagation into DP, they were either problem-specific (relying on custom inference for a single problem type) or did not utilize heuristic search. There was no generic, model-based framework that integrates general-purpose constraint propagation into a DP solver using heuristic search.

2. Methodology

The authors propose a framework that integrates a general-purpose CP solver into the Domain-Independent Dynamic Programming (DIDP) framework (specifically using its Rust interface, RPID).

A. The Hybrid Architecture

The system maintains a "dual view" of the problem:

1. DP View: Handles the state transition system, heuristic search (A* and Complete Anytime Beam Search - CABS), dominance detection, and duplicate detection.
2. CP View: Represents the current state as a Constraint Satisfaction Problem (CSP) to perform inference.

The Integration Process:

• State Representation: When the DP solver considers expanding a state $S$, it constructs a temporary CP model representing the constraints of that state (e.g., unscheduled jobs, resource capacities, time windows).
• Propagation: A general-purpose CP solver (Pumpkin) runs propagation on this model to:
  1. Detect Infeasibility: Determine if the current state or any of its potential successors are impossible to solve (pruning the branch).
  2. Strengthen Dual Bounds: Use the reduced domains ($D'$) from propagation to calculate a tighter lower bound (for minimization problems) than the standard DP dual bound.
• Search Modification: The standard GenSucc function in the DP solver is replaced with GenSuccPropagation. This function:
  • Runs propagation.
  • Filters out infeasible successors.
  • Updates the dual bound for successors using the CP-derived bounds.
  • Passes the refined set of successors to the heuristic search.

B. Key Algorithms Used

• Search: A* and CABS (using $f(S) = g(S) + h(S)$ where $h(S)$ is the dual bound).
• Propagation: Utilizes standard CP propagators like Disjunctive (for non-overlapping tasks) and Cumulative (for resource constraints), employing algorithms like edge-finding and timetable filtering.

3. Key Contributions

1. First Generic Integration: The paper presents the first model-based framework that integrates generic constraint propagation into a DP solver using heuristic search, moving beyond problem-specific heuristics.
2. Dual-View Framework: It successfully combines the strengths of DP (dominance/duplicate detection, heuristic guidance) with CP (strong inference, domain pruning).
3. Implementation in RPID: The framework is implemented within the RPID (Rust Programmable Interface for DIDP), allowing for complex state definitions and fast execution.
4. Empirical Validation: The approach is rigorously tested on three distinct combinatorial problems.

4. Experimental Results

The framework was evaluated on three problems: Single Machine Scheduling with Time Windows (1|ri, δi| P wiTi), Resource Constrained Project Scheduling Problem (RCPSP), and Travelling Salesperson Problem with Time Windows (TSPTW).

• State Expansion Reduction: Constraint propagation significantly reduced the number of state expansions required to solve instances.
• 1|ri, δi| P wiTi: The proposed approach (CABS+CP) solved more instances than the baseline DP solver and the state-of-the-art CP solver (OR-Tools). It was particularly effective on tightly constrained instances (small $\phi$ values).
• RCPSP: The hybrid approach solved significantly more instances per state expansion than the baseline. It proved optimality for more instances than the CP solver alone in many cases.
• TSPTW:
  • For tightly constrained instances (low $\alpha$ and $\beta$ parameters), the hybrid approach reduced state expansions by orders of magnitude compared to pure DP.
  • For loosely constrained instances, the overhead of propagation outweighed the pruning benefits, resulting in fewer solved instances compared to pure DP.
• Runtime Trade-off: While propagation adds computational overhead, the paper concludes that for tightly constrained instances, the reduction in search space (fewer expansions) outweighs the propagation cost. For loose instances, the overhead is currently detrimental.

5. Significance and Future Work

• Bridging Paradigms: This work provides a crucial step in unifying DP and CP, demonstrating that they are complementary rather than mutually exclusive. It allows DP solvers to leverage the powerful inference engines of modern CP solvers without rewriting the search logic.
• Model-Based Flexibility: By using a generic interface, the approach is not limited to specific inference rules, making it applicable to a wide range of combinatorial problems.
• Future Directions:
  • Reducing propagation overhead (e.g., avoiding redundant work when jumping between states).
  • Investigating adaptive strategies to determine when to propagate.
  • Exploring the CP model as a relaxation of the DP model or vice versa.

In summary, the paper demonstrates that integrating generic constraint propagation into heuristic search-based DP solvers creates a powerful hybrid solver that outperforms standalone DP and CP approaches on complex, tightly constrained combinatorial optimization problems.