2026-07-20T10:41:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23866 2025-11-12T13:10:39Z ddc:004 open_access

Transition Dominance in Domain-Independent Dynamic Programming Beck, J. Christopher Kuroiwa, Ryo Lee, Jimmy H. M. Stuckey, Peter J. Zhong, Allen Z. Dominance Dynamic Programming Combinatorial Optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik J. Christopher Beck and Ryo Kuroiwa and Jimmy H. M. Lee and Peter J. Stuckey and Allen Z. Zhong 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.5 urn:nbn:de:0030-drops-238661 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode