Branching is an important component of branch-and-bound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branch-and-bound algorithm, a general branching disjunction of the form $``\pi x \leq \pi_0 \vee \pi x \geq \pi_0 + 1''$, where $\pi, \pi_0$ are integral. We show that the problem of selecting an optimal such disjunction, according to specific criteria described herein, is NP-hard. We further show that the problem remains NP-hard even for binary programs or when considering certain restricted classes of disjunctions. We observe that the problem of deciding whether a given inequality is a split inequality can be reduced to one of the above problems, which leads to a proof that this problem is NP-complete.
Article
View On complexity of Selecting Branching Disjunctions in Integer Programming