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

Carlos Hernández, Jorge A. Baier

Resultado de la investigación: Conference contribution

Resumen

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.

Idioma originalEnglish
Título de la publicación alojadaProceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014
EditoresStefan Edelkamp, Roman Bartak
EditorialAAAI press
Páginas198-199
Número de páginas2
Volumen2014-January
ISBN (versión digital)9781577356769
EstadoPublished - 1 ene 2014
Evento7th Annual Symposium on Combinatorial Search, SoCS 2014 - Prague, Czech Republic
Duración: 15 ago 201417 ago 2014

Conference

Conference7th Annual Symposium on Combinatorial Search, SoCS 2014
PaísCzech Republic
CiudadPrague
Período15/08/1417/08/14

Huella dactilar

Combinatorial optimization

ASJC Scopus subject areas

  • Computer Networks and Communications

Citar esto

Hernández, C., & Baier, J. A. (2014). Toward a search strategy for anytime search in linear space using depth-first branch and bound. En 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. En 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.

Resultado de la investigación: Conference 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. En Edelkamp S, Bartak R, editores, Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014. Vol. 2014-January. AAAI press. 2014. p. 198-199