Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

Authors

  • Daniel Anderson Carnegie Mellon University
  • Gregor Hendel Zuse Institute Berlin
  • Pierre Le Bodic Monash University
  • Merlin Viernickel Zuse Institute Berlin

DOI:

https://doi.org/10.1609/aaai.v33i01.33011427

Abstract

We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for MixedInteger Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.

Downloads

Published

2019-07-17

How to Cite

Anderson, D., Hendel, G., Le Bodic, P., & Viernickel, M. (2019). Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1427-1434. https://doi.org/10.1609/aaai.v33i01.33011427

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization