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

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

doi:10.1609/aaai.v33i01.33011427

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

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

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence
Editors	Pascal Van Hentenryck, Zhi-Hua Zhou
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	1428-1434
Number of pages	8
ISBN (Electronic)	9781577358091
DOIs	https://doi.org/10.1609/aaai.v33i01.33011427
Publication status	Published - 2019
Event	AAAI Conference on Artificial Intelligence 2019 - Honolulu, United States of America Duration: 27 Jan 2019 → 1 Feb 2019 Conference number: 33rd https://aaai.org/Conferences/AAAI-19/

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	AAAI Press
Number	1
Volume	33
ISSN (Print)	2159-5399
ISSN (Electronic)	2374-3468

Conference

Conference	AAAI Conference on Artificial Intelligence 2019
Abbreviated title	AAAI 2019
Country/Territory	United States of America
City	Honolulu
Period	27/01/19 → 1/02/19
Internet address	https://aaai.org/Conferences/AAAI-19/

Access to Document

10.1609/aaai.v33i01.33011427

287142946-oaFinal published version, 402 KB

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

Anderson, Daniel ; Hendel, Gregor ; Le Bodic, Pierre et al. / 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",

note = "AAAI Conference on Artificial Intelligence 2019, AAAI 2019 ; Conference date: 27-01-2019 Through 01-02-2019",

url = "https://aaai.org/Conferences/AAAI-19/",

}

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, Hawaii, 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 et al.
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 proceeding › Conference Paper › Research › peer-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

N1 - Conference code: 33rd

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

T2 - AAAI Conference on Artificial Intelligence 2019

Y2 - 27 January 2019 through 1 February 2019

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). doi: 10.1609/aaai.v33i01.33011427