- On complexity of Selecting Branching Disjunctions in Integer Programming Ashutosh Mahajan (asm4lehigh.edu) Ted Ralphs (tedlehigh.edu) Abstract: 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. Keywords: Generalized branching, Complexity, Disjunctions, Rank Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF]Entry Submitted: 10/17/2008Entry Accepted: 10/17/2008Entry Last Modified: 07/23/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.