Inference-based sensitivity analysis for mixed integer/linear programming

A new method of sensitivity analysis for mixed integer/linear programming ( MILP) is derived from the idea of inference duality. The inference dual of an optimization problem asks how the optimal value can be deduced from the constraints. In MILP, a deduction based on the resolution method of theorem proving can be obtained from the branch-and-cut tree that solves the prima l problem. One can then investigate which perturbations of the problem leav e this proof intact. On this basis it is shown that, in a minimization prob lem, any perturbation that satisfies a certain system of linear inequalitie s will reduce the optimal value no more than a prespecified amount. One can also give an upper bound on the increase in the optimal value that results from a given perturbation. The method is illustrated on two realistic prob lems.