Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound


  • Carlos Hernandez Universidad Catolica de la Santisima Concepcion
  • Jorge Baier Pontificia Universidad Catolica de Chile


Depth-First Branch and Bound, Anytime Search


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.