Branching rules revisited
Zitieren Sie bitte immer diese 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.
Verfasserangaben: | Tobias AchterbergORCiD, Thorsten KochORCiD, Alexander Martin |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Branch-and-Bound; Mixed-integer-programming; Pseudocost-Branching; Reliability-Branching; Strong-Branching; Variable selection |
MSC-Klassifikation: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods |
Datum der Erstveröffentlichung: | 03.05.2004 |
Schriftenreihe (Bandnummer): | ZIB-Report (04-13) |
ZIB-Reportnummer: | 04-13 |
Verlagspublikation: | Appeared in : Operation Research Letters 33 (2005),pp. 42-54. DOI 10.1016/j.orl.2004.04.002 |