License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.23
URN: urn:nbn:de:0030-drops-190605
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19060/
Kuroiwa, Ryo ;
Beck, J. Christopher
Large Neighborhood Beam Search for Domain-Independent Dynamic Programming
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.
BibTeX - Entry
@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/opus/volltexte/2023/19060},
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}
}
