When: April 22, 2015, 12:30 PM
Contact: 608-316-4401, firstname.lastname@example.org
Cut-Generating Functions for Integer Linear Programs
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.
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.
Speaker: Gerard Cornuejols