DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.12

Linear-Memory Beam Search Algorithms in Domain-Independent Dynamic Programming

Authors: Yuxiao Chen and J. Christopher Beck

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

A variety of heuristic search algorithms have been used in Domain-Independent Dynamic Programming (DIDP) for combinatorial optimization. While Complete Anytime Beam Search (CABS) has shown the best performance, it has an exponential memory usage in the worst case. We implement three linear-memory complete beam search algorithms in DIDP: two from the literature, Beam Stack Search (BSS) and Beam search Using Limited discrepancy Backtracking (BULB), and a third that is a novel adaptation of Depth-bounded Discrepancy Search to beam search. Our experimental results show that the linear-memory algorithms exhaust memory on fewer problem instances than CABS and, under restricted memory and extended run-time, BSS and BULB solve more problem instances in more problem classes than CABS. However, in all tested environments, CABS achieves the highest average proportion of instances solved in each of the problem classes, solves the most instances to optimality, and generates solutions with the lowest mean optimality gap.

Cite as

Yuxiao Chen and J. Christopher Beck. Linear-Memory Beam Search Algorithms in Domain-Independent Dynamic Programming. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CP.2026.12,
  author =	{Chen, Yuxiao and Beck, J. Christopher},
  title =	{{Linear-Memory Beam Search Algorithms in Domain-Independent Dynamic Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.12},
  URN =		{urn:nbn:de:0030-drops-266457},
  doi =		{10.4230/LIPIcs.CP.2026.12},
  annote =	{Keywords: Dynamic Programming, Beam Search, Heuristic Search}
}

Search Results

Documents authored by Chen, Yuxiao

Linear-Memory Beam Search Algorithms in Domain-Independent Dynamic Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message