Inference-based sensitivity analysis for mixed integer/linear programming
成果类型：
Article
署名作者：
Dawande, MW; Hooker, JN
署名单位：
International Business Machines (IBM); IBM USA; Carnegie Mellon University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.4.623.12420
发表日期：
2000
页码：
623-634
关键词：
摘要：
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 primal problem. One can then investigate which perturbations of the 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.