Friday, December 14, 2012
3:30 pm, MC 5158

Sanjeeb Dash
IBM TJ Watson Research Center

Cutting planes for mixed-integer programs derived from multi-branch split cuts

Cutting planes (cuts, for short), or inequalities satisfied by integral solutions of systems of linear inequalities, are important tools used in modern solvers for integer programming problems. The split cuts of Cook, Kannan and Schrijver (1990) -- and related Gomory mixed-integer cuts -- form an important class of cutting planes, and have recently been generalized in different ways. Lattice-free cuts, or cuts based on general lattice-free sets in R^n, form one generalization. We study a different generalization called multi-branch split cuts (also called t-branch split cuts by Li and Richard, 2008) and discuss connections with lattice-free cuts.
We show how to express lattice-free cuts as t-branch split cuts for some integer t > 0. We prove an exponential lower bound on t, by constructing lattice-free sets in R^n which cannot be covered by a sub-exponential number of split sets.These results are related to the problem of covering convex sets with strips -- sets of points between two parallel hyperplanes. We use these results to construct a pure cutting plane algorithm for mixed-integer programs. We also settle a conjecture of Li and Richards on t-branch split cuts, and show that there are mixed-integer programs with n+1 variables which are unsolvable by (n-1)-branch split cuts, thus extending the well-known 3-variable example of Cook, Kannan and Schrijver which is unsolvable by split cuts.

This is joint work with Neil Dobbs, Oktay Gunluk, Tomasz Nowicki, and Grzegorz Swirczsz.