Interdiction Branching

Interdiction branching is a branching method for binary integer programs that is designed to overcome some difficulties that may be encountered by branching on a variable dichotomy. Unlike traditional methods, the branching disjunction is selected taking into account the best feasible solution found so far. In particular, the method computes an improving solution cover, which is a set of variables of which at least one must be nonzero in any improving solution. From an improving solution cover, we can obtain a branching disjunction such that 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 trade-off between the size of the enumeration tree and the computational burden of computing the cover. An empirical study shows that such an implementation of the method reduces significantly the size of the enumeration tree compared to branching on variables.