Cutting planes for mixed-integer programs derived...

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

Dr. Sanjeeb Dash
IBM T. J. Watson Research Center, New York

DEI - Sala Seiminari
21 giugno 2012


Cutting planes, or inequalities satisfied by integral solutions of systems of linear inequalities, are important tools used in modern solvers for integer programming problems. Recently, there has been a lot of interest in generalizing the split cutting planes studied by Cook, Kannan and Schrijver (1990) -- and the related MIR cutting planes and Gomory mixed-integer cuts. Lattice-free cuts, or cutting planes based on general lattice-free sets in R^n, form one generalization. We consider a different generalization which we call multi-branch split cuts (also called t-branch split cuts by Li and Richard, 2008) and discuss connections with lattice-free cuts.
In particular we show how to express lattice-free cuts as t-branch split cuts (introduced by Li and Richard, 2008) 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 have a geometric flavor, and are closely 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. Finally, we discuss some computational results with 2-branch split cuts.

Edoardo Amaldi

Area di ricerca:
Analisi applicata dei sistemi e ricerca operativa