Search Results

Documents authored by Kuroiwa, Ryo

Artifact
Software
DOI: 10.4230/artifacts.24205
RPID

Authors: Ryo Kuroiwa and J. Christopher Beck

Abstract
Cite as

Ryo Kuroiwa, J. Christopher Beck. RPID (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24205,
   title = {{RPID}}, 
   author = {Kuroiwa, Ryo and Beck, J. Christopher},
   note = {Software, version 0.1.0., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:9f071b7f5f3daf914c19752ae76692b3a8d1b108;origin=https://github.com/domain-independent-dp/rpid;visit=swh:1:snp:f70c29e2311a12e68fcd938ca0b5d26a248262ce;anchor=swh:1:rev:240549a24194f89ae28f745303df217bc57b6760}{\texttt{swh:1:dir:9f071b7f5f3daf914c19752ae76692b3a8d1b108}} (visited on 2025-08-08)},
   url = {https://github.com/domain-independent-dp/rpid},
   doi = {10.4230/artifacts.24205},
}
Artifact
Software
DOI: 10.4230/artifacts.24206
DIDP Rust Models

Authors: Ryo Kuroiwa

Abstract
Cite as

Ryo Kuroiwa. DIDP Rust Models (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24206,
   title = {{DIDP Rust Models}}, 
   author = {Kuroiwa, Ryo},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:810758e7707cef89647835b7e209d2c94e7bdfd2;origin=https://github.com/Kurorororo/didp-rust-models;visit=swh:1:snp:edeeb24d24acb1253bcb85b3b1c5d1a28406a15e;anchor=swh:1:rev:3bc294f8466c6f9c42b4e90a3ba12eae630fedf0}{\texttt{swh:1:dir:810758e7707cef89647835b7e209d2c94e7bdfd2}} (visited on 2025-08-08)},
   url = {https://github.com/Kurorororo/didp-rust-models},
   doi = {10.4230/artifacts.24206},
}
Document
DOI: 10.4230/LIPIcs.CP.2025.5
Transition Dominance in Domain-Independent Dynamic Programming

Authors: J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

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.
Cite as

J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong. Transition Dominance in Domain-Independent Dynamic Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beck_et_al:LIPIcs.CP.2025.5,
  author =	{Beck, J. Christopher and Kuroiwa, Ryo and Lee, Jimmy H. M. and Stuckey, Peter J. and Zhong, Allen Z.},
  title =	{{Transition Dominance in Domain-Independent Dynamic Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.5},
  URN =		{urn:nbn:de:0030-drops-238661},
  doi =		{10.4230/LIPIcs.CP.2025.5},
  annote =	{Keywords: Dominance, Dynamic Programming, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.23
RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and J. Christopher Beck

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
In domain-independent dynamic programming (DIDP), a problem is formulated as a dynamic programming (DP) model and then solved by a general-purpose solver. In the existing software for DIDP, a model is defined using expressions composed of a predefined set of operations. In this paper, we propose the Rust Programmable Interface for DIDP (RPID), new software for DIDP, where a model is defined by Rust functions. We discuss the design of RPID and compare it with existing DP-based frameworks, including decision diagram-based (DD-based) solvers. In our experiments, RPID is up to hundreds of times faster than the existing DIDP implementation with the same models. In addition, new DIDP models, enabled by the flexibility of RPID, outperform existing models in multiple problem classes. We also show that the relative performance of RPID and existing DD-based solvers depends on problem class with, so far, no clear dominant solver technology.
Cite as

Ryo Kuroiwa and J. Christopher Beck. RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2025.23,
  author =	{Kuroiwa, Ryo and Beck, J. Christopher},
  title =	{{RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.23},
  URN =		{urn:nbn:de:0030-drops-238845},
  doi =		{10.4230/LIPIcs.CP.2025.23},
  annote =	{Keywords: Decision Diagrams \& Dynamic Programming, Modelling \& Modelling Languages}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.23
Large Neighborhood Beam Search for Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and J. Christopher Beck

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Large neighborhood search (LNS) is an algorithmic framework that removes a part of a solution and performs search in the induced search space to find a better solution. While LNS shows strong performance in constraint programming, little work has combined LNS with state space search. We propose large neighborhood beam search (LNBS), a combination of LNS and state space search. Given a solution path, LNBS removes a partial path between two states and then performs beam search to find a better partial path. We apply LNBS to domain-independent dynamic programming (DIDP), a recently proposed generic framework for combinatorial optimization based on dynamic programming. We empirically show that LNBS finds better quality solutions than a state-of-the-art DIDP solver in five out of nine benchmark problem types with a total of 8570 problem instances. In particular, LNBS shows a significant improvement over the existing state-of-the-art DIDP solver in routing and scheduling problems.
Cite as

Ryo Kuroiwa and J. Christopher Beck. Large Neighborhood Beam Search for Domain-Independent Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2023.23,
  author =	{Kuroiwa, Ryo and Beck, J. Christopher},
  title =	{{Large Neighborhood Beam Search for Domain-Independent Dynamic Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.23},
  URN =		{urn:nbn:de:0030-drops-190605},
  doi =		{10.4230/LIPIcs.CP.2023.23},
  annote =	{Keywords: Large Neighborhood Search, Dynamic Programming, State Space Search, Combinatorial Optimization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact