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). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v33i01.33011427
Anderson, Daniel ; Hendel, Gregor ; Le Bodic, Pierre ; Viernickel, Merlin. / Clairvoyant restarts in Branch-and-Bound search using online tree-size estimation. Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence. editor / Pascal Van Hentenryck ; Zhi-Hua Zhou. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. pp. 1428-1434 (Proceedings of the AAAI Conference on Artificial Intelligence; 1).
@inproceedings{189abd03a19a42a581051889f216193c,
title = "Clairvoyant restarts in Branch-and-Bound search using online tree-size estimation",
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.",
author = "Daniel Anderson and Gregor Hendel and {Le Bodic}, Pierre and Merlin Viernickel",
year = "2019",
doi = "10.1609/aaai.v33i01.33011427",
language = "English",
series = "Proceedings of the AAAI Conference on Artificial Intelligence",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
number = "1",
pages = "1428--1434",
editor = "{Van Hentenryck}, {Pascal } and Zhou, {Zhi-Hua }",
booktitle = "Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence",
address = "United States of America",

}

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., 7399, Proceedings of the AAAI Conference on Artificial Intelligence, no. 1, vol. 33, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 1428-1434, AAAI conference on Artificial Intelligence 2019, Honolulu, United States of America, 27/01/19. https://doi.org/10.1609/aaai.v33i01.33011427

Clairvoyant restarts in Branch-and-Bound search using online tree-size estimation. / Anderson, Daniel ; Hendel, Gregor; Le Bodic, Pierre; Viernickel, Merlin.

Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence. ed. / Pascal Van Hentenryck; Zhi-Hua Zhou. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 1428-1434 7399 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33, No. 1).

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

TY - GEN

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

AU - Anderson, Daniel

AU - Hendel, Gregor

AU - Le Bodic, Pierre

AU - Viernickel, Merlin

PY - 2019

Y1 - 2019

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

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

U2 - 10.1609/aaai.v33i01.33011427

DO - 10.1609/aaai.v33i01.33011427

M3 - Conference Paper

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 1428

EP - 1434

BT - Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence

A2 - Van Hentenryck, Pascal

A2 - Zhou, Zhi-Hua

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

ER -

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