Return to Colloquia & Seminar listing
Optimality Certificates and Sensitivity Analysis for Mixed Integer Programming Problems
Optimization| 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.