Abstract
Branch and bound algorithms for Mixed-Integer Linear Programming (MILP) almost universally branch on a single variable to create disjunctions. General linear expressions involving multiple variables are another option for branching disjunctions, but are not used for two main reasons: (i) descendent LPs tend to solve more slowly because of the added constraints, so the overall solution time is increased, and (ii) it is difficult to quickly find an effective general disjunction. We study the use of general disjunctions to reach the first MILP-feasible solution quickly, showing for the first time that general disjunctions can provide speed improvements for hard MILP models. The speed-up is due to new and efficient ways to (i) trigger the inclusion of a general disjunction only when it is likely to be beneficial, and (ii) construct effective general disjunctions very quickly. Our empirical results show performance improvements versus a state of the art commercial MILP solver. (C) 2013 Elsevier Ltd. All rights reserved.