Wednesday 20 November 2013, 11.00am-12.00pm
NAB 2.04, New Academic Building
Sanjeeb Dash
IBM Thomas J. Watson Research Center, New York
Personal Profile
Abstract:
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. Split cuts -- which are related to Gomory mixed-integer cuts -- were first studied by Cook, Kannan and Schrijver (1990). In this talk we present computational results on the use of split cuts in two different contexts. We consider a family of quadratic unconstrained boolean optimization problems recently used in tests on the DWave quantum computer and discuss how they can be solved using special families of split cuts in reasonable time. We also show how to accelerate the solution of a special class of two-stage stochastic integer programming problems using split cuts.
This is joint work with Merve Bodur, Marcos Goycoolea, Oktay Gunluk, and Jim Luedtke.