Gérard P. Cornuéjols, Prof. at Carnegie Mellon University
Date and Time: Apr 22, 2015 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building
Cutting planes have become a key component of integer programming solvers. Most cutting planes in use currently are valid for Gomory's corner relaxation, which is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this talk, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on a new concept, the notion of generalized symmetry condition. We also extend to our setting the 2-slope theorem of Gomory and Johnson for extreme cut-generating functions. This talk is based on joint work with Sercan Yildiz.