  


On complexity of Selecting Branching Disjunctions in Integer Programming
Ashutosh Mahajan (asm4lehigh.edu) Abstract: Branching is an important component of branchandbound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branchandbound 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 NPhard. We further show that the problem remains NPhard 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 NPcomplete. Keywords: Generalized branching, Complexity, Disjunctions, Rank Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 10/17/2008 Modify/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  