Optimization Online


On complexity of Selecting Branching Disjunctions in Integer Programming

Ashutosh Mahajan (asm4***at***lehigh.edu)
Ted Ralphs (ted***at***lehigh.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 )


Download: [PDF]

Entry Submitted: 10/17/2008
Entry Accepted: 10/17/2008
Entry Last Modified: 07/23/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society