This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Dawande, M. W. Articles by Hooker, J. N. Search for Related Content

Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming

IBM, T. J. Watson Research Center, Yorktown Heights, New York 10598
Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
milind{at}watson.ibm.com
jh38{at}andrew.cmu.edu

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 oftheorem proving can be obtained from the branch-and-cut tree that solves the primal problem. One can then investigate which perturbations ofthe problem leave this proof intact. On this basis it is shown that, in a minimization problem, any perturbation that satisfies a certain system of linear inequalities 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 problems.

Subject classifications: Sensitivity analysis: sensitivity analysis for mixed integer programming; Integer programming.
History: Received February 1997; revision received February 1998; revision received June 1998; revision received December 1998; accepted January 1999.