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

# Faster Integer Feasibility in MIPs by Branching to Force Change

## John W. Chinneck – Professeur de recherche émérite, 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.