Faster Integer Feasibility in MIPs by Branching to Force Change
John W. Chinneck – Professor, Department of Systems and Computer Engineering, Carleton University, Canada
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.