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

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

Fingerprint

Combinatorial optimization

ASJC Scopus subject areas

  • Computer Networks and Communications

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.
Hernández, Carlos ; Baier, Jorge A. / Toward a search strategy for anytime search in linear space using depth-first branch and bound. Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014. editor / Stefan Edelkamp ; Roman Bartak. Vol. 2014-January AAAI press, 2014. pp. 198-199
@inproceedings{3623dd0bab3a4299aacc0a3e95fb9988,
title = "Toward a search strategy for anytime search in linear space using depth-first branch and bound",
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.",
author = "Carlos Hern{\'a}ndez and Baier, {Jorge A.}",
year = "2014",
month = "1",
day = "1",
language = "English",
volume = "2014-January",
pages = "198--199",
editor = "Stefan Edelkamp and Roman Bartak",
booktitle = "Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014",
publisher = "AAAI press",

}

Hernández, C & Baier, JA 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, AAAI press, pp. 198-199, 7th Annual Symposium on Combinatorial Search, SoCS 2014, Prague, Czech Republic, 15/08/14.

Toward a search strategy for anytime search in linear space using depth-first branch and bound. / Hernández, Carlos; Baier, Jorge A.

Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014. ed. / Stefan Edelkamp; Roman Bartak. Vol. 2014-January AAAI press, 2014. p. 198-199.

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

TY - GEN

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

AU - Hernández, Carlos

AU - Baier, Jorge A.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85048707442&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85048707442

VL - 2014-January

SP - 198

EP - 199

BT - Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014

A2 - Edelkamp, Stefan

A2 - Bartak, Roman

PB - AAAI press

ER -

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