Search Results

Documents authored by Kuroiwa, Ryo

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}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact