The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Cut-Generating Functions for Integer Linear Programs

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.