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

1 Citation (Scopus)

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.

Original 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