Spring 2013 Seminar Series

DATE: April 11th
LOCATION: E51-315
TIME: 4:15pm
Reception immediately following

SPEAKER:
Egon Balas

TITLE
On Cut Generating Sets and Their Use in Mixed Integer Programming

ABSTRACT
A new paradigm for generating cuts in mixed integer programming (Balas and Margot, 2011) identifies a set Q of boundary points of a lattice-free polyhedron S, such that the reverse polar of Q provides valid cuts. We call Q a cut generating set. We discuss ways of generating such sets and their properties. We compare the cuts generated from such sets, which we call generalized or look-ahead intersection cuts, to cuts belonging to known families. In particular, we show that the new paradigm offers a way to generate in a non-recursive fashion deep cuts that can otherwise be generated only through several iterations of one of the standard procedures. There is a large variety of possible ways to apply the principles of this approach, and we discuss some of them . Finally, we discuss implementation aspects and some preliminary computational experience.

 

This talk is based on joint work with Francois Margot and Selvaprabu Nadarajah