MILP sensitivity analysis for the objective function coeffcients

The talk introduces a new approach to sensitivity analysis of the objective function coeffcients in mixed-integer linear programming (MILP). We determine the maximal region of the coeffcients for which the current solution remains optimal. The region is maximal in the sense that for variations beyond this region, the optimal solution changes. For variations in a single objective function coeffcients, we show how to obtain the region by bi-objective mixed-integer linear programming. In particular, we prove that it suffices to determine the two extreme nondominated points adjacent to the optimal solution of the MILP problem. The methodology extends to simultaneous changes to two or more coeffcients by use of multi-objective analysis. It can likewise be extended to sensitivity analysis in multi-objective MILP.

Download Slides