Estimating the size of search trees by sampling with domain knowledge

Gleb Belov, Samuel Esler, Dylan Fernando, Pierre Le Bodic, George L. Nemhauser

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

Abstract

We show how recently-defined abstract models of the Branch & Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.

LanguageEnglish
Title of host publicationProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)
EditorsCarles Sierra
Place of PublicationCanada
PublisherInternational Joint Conferences on Artificial Intelligence
Pages473-479
Number of pages7
ISBN (Electronic)9780999241103
DOIs
Publication statusPublished - 1 Jan 2017
EventInternational Joint Conference on Artificial Intelligence 2017 - Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017
Conference number: 26th
https://ijcai-17.org/

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2017
Abbreviated titleIJCAI 2017
CountryAustralia
CityMelbourne
Period19/08/1725/08/17
Internet address

Cite this

Belov, G., Esler, S., Fernando, D., Le Bodic, P., & Nemhauser, G. L. (2017). Estimating the size of search trees by sampling with domain knowledge. In C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) (pp. 473-479). Canada: International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2017/67
Belov, Gleb ; Esler, Samuel ; Fernando, Dylan ; Le Bodic, Pierre ; Nemhauser, George L. / Estimating the size of search trees by sampling with domain knowledge. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17). editor / Carles Sierra. Canada : International Joint Conferences on Artificial Intelligence, 2017. pp. 473-479
@inproceedings{ff26a928930f4110ab24011bf44fddfd,
title = "Estimating the size of search trees by sampling with domain knowledge",
abstract = "We show how recently-defined abstract models of the Branch & Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.",
author = "Gleb Belov and Samuel Esler and Dylan Fernando and {Le Bodic}, Pierre and Nemhauser, {George L.}",
year = "2017",
month = "1",
day = "1",
doi = "10.24963/ijcai.2017/67",
language = "English",
pages = "473--479",
editor = "Carles Sierra",
booktitle = "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)",
publisher = "International Joint Conferences on Artificial Intelligence",

}

Belov, G, Esler, S, Fernando, D, Le Bodic, P & Nemhauser, GL 2017, Estimating the size of search trees by sampling with domain knowledge. in C Sierra (ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17). International Joint Conferences on Artificial Intelligence, Canada, pp. 473-479, International Joint Conference on Artificial Intelligence 2017, Melbourne, Australia, 19/08/17. https://doi.org/10.24963/ijcai.2017/67

Estimating the size of search trees by sampling with domain knowledge. / Belov, Gleb; Esler, Samuel; Fernando, Dylan; Le Bodic, Pierre; Nemhauser, George L.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17). ed. / Carles Sierra. Canada : International Joint Conferences on Artificial Intelligence, 2017. p. 473-479.

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

TY - GEN

T1 - Estimating the size of search trees by sampling with domain knowledge

AU - Belov, Gleb

AU - Esler, Samuel

AU - Fernando, Dylan

AU - Le Bodic, Pierre

AU - Nemhauser, George L.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We show how recently-defined abstract models of the Branch & Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.

AB - We show how recently-defined abstract models of the Branch & Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.

UR - http://www.scopus.com/inward/record.url?scp=85031916096&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2017/67

DO - 10.24963/ijcai.2017/67

M3 - Conference Paper

SP - 473

EP - 479

BT - Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

A2 - Sierra, Carles

PB - International Joint Conferences on Artificial Intelligence

CY - Canada

ER -

Belov G, Esler S, Fernando D, Le Bodic P, Nemhauser GL. Estimating the size of search trees by sampling with domain knowledge. In Sierra C, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17). Canada: International Joint Conferences on Artificial Intelligence. 2017. p. 473-479 https://doi.org/10.24963/ijcai.2017/67