Clairvoyant restarts in Branch-and-Bound search using online tree-size estimation

Daniel Anderson, Gregor Hendel, Pierre Le Bodic, Merlin Viernickel

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence
EditorsPascal Van Hentenryck, Zhi-Hua Zhou
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1428-1434
Number of pages8
ISBN (Electronic)9781577358091
DOIs
Publication statusPublished - 2019
EventAAAI conference on Artificial Intelligence 2019 - Honolulu, United States of America
Duration: 27 Jan 20191 Feb 2019
Conference number: 33rd
https://aaai.org/Conferences/AAAI-19/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Number1
Volume33
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI conference on Artificial Intelligence 2019
Abbreviated titleAAAI 2019
CountryUnited States of America
CityHonolulu
Period27/01/191/02/19
Internet address

Cite this

Anderson, D., Hendel, G., Le Bodic, P., & Viernickel, M. (2019). Clairvoyant restarts in Branch-and-Bound search using online tree-size estimation. In P. Van Hentenryck, & Z-H. Zhou (Eds.), Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence (pp. 1428-1434). [7399] (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33, No. 1). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v33i01.33011427