branching The basic idea of this strategy is to keep track for each variable the change in the objective function when this variable was previously chosen as the variable to branch on. The strategy then chooses the variable that is predicted to have the most change on the objective function based on past changes when it was chosen as the branching variable. Note that pseudo cost branching is initially uninformative in the search since few variables have been branched on. Strong branching Strong branching involves testing which of the candidate variable gives the best improvement to the objective function before actually branching on them. Full strong branching tests all candidate variables and can be computationally expensive. The computational cost can be reduced by only considering a subset of the candidate variables and not solving each of the corresponding LP relaxations to completion. There are also a large number of variations of these branching strategies, such as using strong branching early on when pseudo cost branching is relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative. References External links Mixed Integer Programming SCIP: framework for branch-cut-and-price and a mixed integer programming solver ABACUS – A Branch-And-CUt System – open source software COIN-OR Cbc – open source software on GitHub Combinatorial optimization Optimization algorithms and methods