Domain-Independent Dynamic Programming with Constraint Propagation

Technical Deep Dive: Domain-Independent Dynamic Programming with Constraint Propagation

Overview

This paper presents a framework for integrating constraint propagation into a Dynamic Programming (DP) solver, enabling it to prune states and transitions using constraint propagation. The key contributions are:

• A dual view of the problem, using a state-based DP view and an integer-based Constraint Programming (CP) view, providing:
  • Dominance and duplicate detection, and heuristic search using the DP view
  • Strong inference techniques for constraints using the CP view, allowing pruning of states and strengthening of the dual bound
• 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

The authors evaluate their framework on three combinatorial optimization problems: Single Machine Scheduling with Time Windows, the Resource Constrained Project Scheduling Problem, and the Travelling Salesperson Problem with Time Windows. The results show that constraint propagation significantly reduces the number of state expansions, enabling their approach to solve more instances than a DP solver alone for the first two problems, and tightly constrained instances of the third.

Methodology

The authors create a framework that integrates constraint propagation from CP with DP modeling. The key components are:

1. The DP model, defined using the Domain-Independent Dynamic Programming (DIDP) framework, which provides:
   • State-based representation of the problem
   • Dual bounds computation
   • Dominance and duplicate detection
   • Heuristic search algorithms like A* and Complete Anytime Beam Search
2. The constraint programming solver, which provides:
   • Constraint propagation to prune infeasible states and strengthen the dual bound
   • Generic constraint propagation algorithms like edge-finding and time-table filtering

The authors implement their approach using the RPID (Rust Programmable Interface for DIDP) and the Pumpkin CP solver. The integration is done by:

• Replacing the state generation function GenSucc(S) with a new function GenSuccPropagation(S, Primal) that creates a CP model, propagates it, and checks for infeasibility
• Using the strengthened dual bound from the CP solver in addition to the DP dual bound

Experimental Setup

The authors evaluate their approach on three combinatorial optimization problems:

1. Single Machine Scheduling with Time Windows (1|r_i, δ_i|∑w_iT_i): 900 instances with 50 jobs, varying instance constrainedness.
2. Resource Constrained Project Scheduling Problem (RCPSP): 480 instances from the PSPLIB benchmark.
3. Travelling Salesperson Problem with Time Windows (TSPTW): 180 instances from the literature.

They compare their approach (A\/CABS+CP) to the baseline DP solvers (A\/CABS) and the state-of-the-art CP solver OR-Tools. The experiments were run on an Intel Xeon Gold 6248R 24C 3.0GHz processor with a 30-minute time limit and 16GB of memory.

Results

The key findings are:

1. 1|r_i, δ_i|∑w_iT_i:
   • Constraint propagation significantly reduces the number of state expansions, enabling the authors' approach to solve more instances than the DP baseline.
   • The benefits of propagation are most pronounced for tightly constrained instances.
2. RCPSP:
   • Constraint propagation greatly increases the number of instances solved per state expansion compared to the DP baseline.
   • The authors' approach outperforms OR-Tools in terms of optimality gap on numerous instances.
3. TSPTW:
   • For the general instance set, constraint propagation does not improve performance due to the overhead outweighing the benefits of pruning.
   • However, for tightly constrained instances, the authors' approach solves significantly more instances per state expansion than the DP baseline.

Interpretation

The results demonstrate the value of integrating constraint propagation into a DP solver, especially for problems with tight constraints. The dual view of the problem, combining the strengths of DP (heuristic search, dominance detection) and CP (constraint propagation), allows the authors' approach to outperform both standalone DP and CP solvers on several benchmarks.

The performance gains are most pronounced for tightly constrained instances, where constraint propagation is able to significantly prune the search space. This suggests that the complementary strengths of DP and CP can be effectively leveraged for solving challenging combinatorial optimization problems.

Limitations & Uncertainties

• The authors note that further work is needed to reduce the overhead of constraint propagation, as it can outweigh the benefits for loosely constrained instances.
• The evaluation is limited to three specific combinatorial optimization problems. The generalizability of the approach to a broader class of problems is not fully established.
• The authors do not explore the impact of different constraint propagation algorithms or hybridization strategies beyond the basic integration presented in the paper.

Future Work

Based on the findings, the authors suggest several directions for future research:

• Investigating the integration of DP solvers with other techniques beyond just CP, such as decision diagrams or linear programming.
• Exploring ways to reduce the overhead of constraint propagation, for example by avoiding redundant work when jumping between states.
• Examining what is represented in the CP model, such as using the DP model as a relaxation and the CP model to capture the missing elements.

Overall, this work provides a significant step forward in understanding the value of integrating constraint propagation into DP solvers, and opens up promising avenues for further research in this area.