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/2008
Entry Accepted: 10/17/2008
Entry Last Modified: 07/23/2010

Modify/Update this entry