Branching on History Information
Please always quote using this URN: urn:nbn:de:0297-zib-6990
- Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy.
Download full text files
Additional Services
| Author: | Tobias AchterbergORCiD, Thorsten KochORCiD, Alexander Martin |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Branch-and-Bound; Branching Rules; Mixed Integer Programming; Pseudocost Branching |
| MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Wxx Algorithms (For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx) / 68W01 General |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods | |
| Date of first Publication: | 2002/10/04 |
| Series (Serial Number): | ZIB-Report (02-32) |
| ZIB-Reportnumber: | 02-32 |
