Groupe d’études et de recherche en analyse des décisions

Faster Integer Feasibility in MIPs by Branching to Force Change

John W. Chinneck 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.