Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming

M. W. Dawande () and J. N. Hooker ()
Additional contact information
M. W. Dawande: IBM, T. J. Watson Research Center, Yorktown Heights, New York 10598
J. N. Hooker: Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2000, vol. 48, issue 4, 623-634

Abstract: 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.

Keywords: Sensitivity analysis: sensitivity analysis for mixed integer programming; Integer programming (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.4.623.12420 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:4:p:623-634

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().