Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Optimality Certificates and Sensitivity Analysis for Mixed Integer Programming Problems


Speaker: Babak Moazzez, UC Davis
Location: 3106 MSB
Start time: Thu, Oct 23 2014, 11:00AM

After solving a mixed integer program, a certificate can be used the check the optimality of the solution at hand. We present generalized subadditive generator functions which can be used as certificates of optimality and also as a tool for sensitivity analysis for MILPs. These are subadditive dual feasible functions with desirable properties. The certificates generated are much easier to check compared with the time needed to solve the optimization problem. Same functions can be used as a tool for sensitivity analysis and most notions such as reduced costs will carry over from linear programming to mixed integer programming.