Branching rules revisited

被引：262

作者：

Achterberg, T ^{[1
]}

Koch, T

Martin, A

机构：

[1] Konrad Zuse Zentrum Informationstech, Berlin, Germany

[2] Tech Univ Darmstadt, D-64289 Darmstadt, Germany

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 01期

关键词：

mixed-integer-programming; branch-and-bound; variable selection; pseudocost-branching; strong-branching; reliability-branching;

D O I：

10.1016/j.orl.2004.04.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a new generalization called reliability branching of today's state-of-the-art strong branching and pseudocost branching strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed new strategy. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：42 / 54

页数：13

共 15 条

[1] ACHTERBERG T, 2003, MIPLIB 2003
[2] [Anonymous], 1995, 9505 DIMACS
[3] Benichou M, 1971, MATH PROGRAM, V1, P76, DOI DOI 10.1007/BF01584074
[4] Decomposing matrices into blocks
Borndörfer, R
Ferreira, CE
Martin, A
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 9 (01) : 236 - 269
[5] CLOCHARD JM, 1993, P 3 IPCO C, P291
[6] FOURER B, 2003, OR MS TODAY, V30, P34
[7] *ILOG CPLEX, 2003, REF MAN
[8] LAND AH, 1979, ANN DISCRETE MATH, V5, P221
[9] LEIPERT S, 1996, VBCTOOL GRAPHICAL IN
[10] Computational study of search strategies for mixed integer programming
Linderoth, JT
Savelsbergh, MWP
[J]. INFORMS JOURNAL ON COMPUTING, 1999, 11 (02) : 173 - 187

← 1 2 →