Estimating the Size of Search Trees by Sampling with Domain Knowledge

被引：0

作者：

Belov, Gleb ^{[1
]}

Esler, Samuel ^{[1
]}

Fernando, Dylan ^{[1
]}

Le Bodic, Pierre ^{[1
]}

Nemhauser, George L. ^{[2
]}

机构：

[1] Monash Univ, Fac Informat Technol, Clayton, Vic, Australia

[2] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

PROCEEDINGS OF THE TWENTY-SIXTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE | 2017年

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：473 / 479

页数：7

共 15 条

[1]

Achterberg T, 2007, THESIS TU BERLIN, DOI [10.14279/depositonce-1634, DOI 10.14279/DEPOSITONCE-1634]

[2] SCIP: solving constraint integer programs [J].

Achterberg, Tobias .

MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) :1-41

[3]

[Anonymous], 2006, the Twenty-First National Conference on Artificial intelligence

[4] HEURISTIC SAMPLING - A METHOD FOR PREDICTING THE PERFORMANCE OF TREE SEARCHING PROGRAMS [J].

CHEN, PC .

SIAM JOURNAL ON COMPUTING, 1992, 21 (02) :295-315

[5] Early estimates of the size of branch-and-bound trees [J].

Cornuéjols, G ;

Karamanov, M ;

Li, YJ .

INFORMS JOURNAL ON COMPUTING, 2006, 18 (01) :86-96

[6] ESTIMATING EFFICIENCY OF BACKTRACK PROGRAMS [J].

KNUTH, DE .

MATHEMATICS OF COMPUTATION, 1975, 29 (129) :121-136

[7] MIPLIB 2010: Mixed integer programming library version 5 [J].

Koch T. ;

Achterberg T. ;

Andersen E. ;

Bastert O. ;

Berthold T. ;

Bixby R.E. ;

Danna E. ;

Gamrath G. ;

Gleixner A.M. ;

Heinz S. ;

Lodi A. ;

Mittelmann H. ;

Ralphs T. ;

Salvagnin D. ;

Steffy D.E. ;

Wolter K. .

Mathematical Programming Computation, 2011, 3 (2) :103-163

[8]

Le Bodic P, 2017, MATH PROGRAM, V166, P369, DOI 10.1007/s10107-016-1101-8

[9]

Lelis L.H. S., 2013, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI'13, P594

[10]

Lobjois L, 1998, FIFTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98) AND TENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICAL INTELLIGENCE (IAAI-98) - PROCEEDINGS, P353

← 1 2 →