Transition Dominance in Domain-Independent Dynamic Programming

J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, Allen Z. ZhongCP 2025 · OpenReview

TL;DR

This paper introduces "transition dominance" to Domain-Independent Dynamic Programming (DIDP), a technique that allows solvers to prune search paths when one transition is provably worse than another. By providing a new interface for defining these dominance rules and using state functions to cache computations, the authors achieve significant speedups (5-10x on average) in solving complex combinatorial optimization problems.

What Problem Does This Paper Address?

Traditional dynamic programming (DP) solutions are often hard-coded for specific problems, making them inflexible and difficult to adapt. Domain-Independent Dynamic Programming (DIDP) aims to solve this by separating the DP model specification from the solving process, allowing for easier experimentation with different search algorithms and DP models. However, efficiently solving complex DP problems still requires techniques to prune the search space. While state dominance (comparing entire states) exists, this paper addresses the need for "transition dominance" – a way to prune search paths based on the relative performance of individual transitions from a given state, without requiring extra memory for state comparisons.

Methods

The core contribution is the formal definition of transition dominance within the DIDP framework. This concept states that if transition $\tau$ consistently leads to a better or equal solution than transition $\tau'$ from a state $S$, then $\tau'$ can be safely ignored. To facilitate this, the authors introduce:

  • A Transition Dominance Interface: A mechanism within the DIDP modeling language (DyPDL) to explicitly define transition dominance rules. This separates dominance information from core transition preconditions, making models cleaner.
  • State Functions: A way to define and cache the results of expressions involving state variables. This is crucial for efficiently verifying transition dominance, as these expressions (e.g., calculating completion times) can be computationally expensive and appear in multiple places (cost, effects, dominance conditions).

The paper also discusses how to handle potential issues like reflexive dominance rules by using contracted transition dominance graphs and exploring the trade-offs between using the interface versus embedding dominance as preconditions.

Datasets

The paper evaluates their approach on seven combinatorial optimization problems:

  • One Machine Scheduling Minimizing Total Weighted Tardiness (1|ri|∑wiTi)
  • Aircraft Landing Problem (ALP)
  • Talent Scheduling (Talent-Sched)
  • Discrete Lot Sizing Problem (DSLP)
  • Graph-Clear
  • Orienteering Problem with Time Window (OPTW)
  • Travelling Salesman Problem with Time Windows and Makespan Objective (TSPTW-M)

For these problems, they either modify existing DyPDL models or create new ones, and use benchmark instances from the literature. Specific details on instance generation for the newly modeled problems are provided.

Key Insights and Ideas

  • Transition Dominance is a Powerful Pruning Tool: By focusing on the relative performance of individual transitions, rather than entire states, transition dominance offers a complementary and effective way to reduce the search space in DP.
  • Efficiency is Key: The effectiveness of transition dominance hinges on efficient computation. The introduction of state functions to cache intermediate results is critical for making this technique practical, especially when dominance conditions involve complex expressions.
  • Separation of Concerns: The explicit interface for transition dominance, distinct from transition preconditions, leads to cleaner and more understandable models. This separation allows solvers to treat dominance information as a distinct optimization hint.
  • Generalizability: The paper demonstrates that transition dominance patterns, often related to advancing or shifting transitions, appear across diverse problem domains, suggesting a potential for automated discovery of such rules.

Key Results

The experimental evaluation shows significant improvements when incorporating transition dominance and state functions:

  • Speedup: On average, a 5 to 10 times speed-up was observed across various search algorithms (ACPS, CABS, CAASDY) compared to baseline models.
  • Coverage: The "+D+S" (dominance + state functions) configuration enabled solvers to solve 420, 450, and 426 more instances for ACPS, CAASDy, and CABS, respectively, within the given limits.
  • Optimality Gap: The average optimality gap was reduced by up to 0.155.
  • Expanded Nodes: Transition dominance alone reduced the number of expanded nodes across most problems, except for Graph-Clear where the summation computations were costly without state functions.

Limitations and Future Work

  • Computational Cost of Dominance: For problems like Graph-Clear, evaluating transition dominance conditions involving set summations can be computationally expensive if not optimized with state functions.
  • Automatic Discovery: The authors suggest that future work could focus on automatically extracting transition dominance rules by analyzing DyPDL models, as recurring patterns were observed.
  • Trade-offs in State Functions: The paper notes that for simple expressions, caching via state functions might not always be beneficial and can even add overhead. Analyzing the trade-off between recomputation and caching for state functions is an interesting research direction.
  • Tie-breaking: While the framework supports transition dominance, handling situations where multiple transitions dominate each other symmetrically might require careful implementation or further research.

Summary updated

Abstract

Domain-independent dynamic programming (DIDP) is a model-based paradigm for dynamic programming (DP) that enables users to define DP models based on a state transition system. Heuristic search-based solvers have demonstrated strong performance in solving combinatorial optimization problems. In this paper, we formally define transition dominance in DIDP, where one transition consistently leads to better solutions than another, allowing the search process to safely ignore dominated transitions. To facilitate the efficient use of transition dominance, we introduce an interface for defining transition dominance and propose the use of state functions to cache values, thereby avoiding redundant computations when verifying transition dominance. Experimental results on DP models across multiple problem classes indicate that incorporating transition dominance and state functions yields a 5 to 10 times speed-up on average for different search algorithms within the DIDP framework compared to the baseline.
BibTeX
@inproceedings{beck2025transition,
  author = {J. Christopher Beck and Ryo Kuroiwa and Jimmy H. M. Lee and Peter J. Stuckey and Allen Z. Zhong},
  title = {{Transition Dominance in Domain-Independent Dynamic Programming}},
  booktitle = {CP},
  year = {2025},
  url = {https://openreview.net/forum?id=ncAVPyTNzg},
}
Figure