Toward a search strategy for anytime search in linear space using depth-first branch and bound

Carlos Hernández, Jorge A. Baier

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Depth-First Branch and Bound (DFBnB) is an anytime algorithm for solving combinatorial optimization problems. In this paper we present a weighted version of DFBnB, wDFBnB, which incorporates standard techniques for using weights in heuristic search and offers suboptimality guarantees. Our main contribution drawn from a preliminary evaluation is the observation that wDFBnB, used along with automated or hand-crafted weight schedules, can significantly outperform DFBnB both in terms of anytime behavior and convergence to the optimal. We think this small study calls for more research on the design of automated weight schedules that could provide superior anytime performance across a wider range of domains.

Original languageEnglish
Title of host publicationProceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014
EditorsStefan Edelkamp, Roman Bartak
PublisherAAAI press
Pages198-199
Number of pages2
Volume2014-January
ISBN (Electronic)9781577356769
Publication statusPublished - 1 Jan 2014
Event7th Annual Symposium on Combinatorial Search, SoCS 2014 - Prague, Czech Republic
Duration: 15 Aug 201417 Aug 2014

Conference

Conference7th Annual Symposium on Combinatorial Search, SoCS 2014
CountryCzech Republic
CityPrague
Period15/08/1417/08/14

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Toward a search strategy for anytime search in linear space using depth-first branch and bound'. Together they form a unique fingerprint.

  • Cite this

    Hernández, C., & Baier, J. A. (2014). Toward a search strategy for anytime search in linear space using depth-first branch and bound. In S. Edelkamp, & R. Bartak (Eds.), Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014 (Vol. 2014-January, pp. 198-199). AAAI press.