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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Tobias Achterberg, Thorsten Koch, 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)
Published in:Appeared in : Operation Research Letters 33 (2005),pp. 42-54. DOI 10.1016/j.orl.2004.04.002