Branching rules revisited
Please always quote using this URN: urn:nbn:de:0297-zib-7886
- Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl 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 newstrategy.
Author: | Tobias AchterbergORCiD, Thorsten KochORCiD, Alexander Martin |
---|---|
Document Type: | ZIB-Report |
Tag: | Branch-and-Bound; Mixed-integer-programming; Pseudocost-Branching; Reliability-Branching; Strong-Branching; Variable selection |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods |
Date of first Publication: | 2004/05/03 |
Series (Serial Number): | ZIB-Report (04-13) |
ZIB-Reportnumber: | 04-13 |
Published in: | Appeared in : Operation Research Letters 33 (2005),pp. 42-54. DOI 10.1016/j.orl.2004.04.002 |