2026-07-21T11:55:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19060 2024-03-06T11:03:24Z ddc:004 open_access

Large Neighborhood Beam Search for Domain-Independent Dynamic Programming Kuroiwa, Ryo Beck, J. Christopher Large Neighborhood Search Dynamic Programming State Space Search Combinatorial Optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryo Kuroiwa and J. Christopher Beck 2023 Is Part Of LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2023.23 urn:nbn:de:0030-drops-190605 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode