Most mixed-integer linear programming branching heuristics try to find the branch that has the most impact on the objective function. A different approach is needed when the goal is reaching the first integer-feasible solution quickly. Intuition says that branching to maximize the probability of reaching a feasible solution is best. This is wrong: the most effective strategies branch in the direction that has the least probability of reaching feasibility! This gives rise to the new principle of branching to force change.
Groupe d’études et de recherche en analyse des décisions