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

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Tobias Achterberg, Thorsten Koch, 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)