  


Interdiction Branching
Andrea Lodi (andrea.lodiunibo.it) Abstract: This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the method is based on computing an improving solution cover, which is a set of variables of which at least one must be nonzero in any improving solution. From an improvingsolution cover, we can obtain a branching disjunction with desirable properties. Any minimal such cover yields a disjunction in which multiple variables are fixed in each child node and for which each child node is guaranteed to contain at least one improving solution. Computing a minimal improving solution cover amounts to solving a discrete bilevel program, which is difficult in general. In practice, a solution cover, although not necessarily minimal nor improving, can be found using a heuristic that achieves a profitable tradeoff between the size of the enumeration tree and the computational burden of computing the cover. An empirical study on a test suite of difficult binary knapsack and stable set problems shows that an implementation of the method dramatically reduces the size of the enumeration tree compared to branching on variables, yielding significant savings in running times. Keywords: Integer Programming, Branching, Branch and Bound, Branch and Cut, Knapsack, Stable Set, Bilevel Programming Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Integer Programming (01 Programming ) Citation: Technical Report, COR@L Laboratory, Lehigh University. Download: [PDF] Entry Submitted: 09/30/2011 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  