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
11.00

Abstract:

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.

Contatti:
Edoardo Amaldi

Area di ricerca:
Analisi applicata dei sistemi e ricerca operativa