On the relationship between e-sensitivity analysis and sensitivity analysis using an optimal basis

ε-sensitivity analysis is a kind of method for performing sensitivity analysis for linear programming. Its main advantage is that it can be directly applied for interior-point methods with a little computation. Although ε-sensitivity analysis was proposed several years ago, there have been no studies on its relationship with other sensitivity analysis methods. In this paper, we discuss the relationship between ε-sensitivity analysis and sensitivity analysis using an optimal basis. First, we present a property of ε-sensitivity analysis, from which we derive a simplified formula for finding the characteristic region of ε-sensitivity analysis. Next, using the simplified formula, we examine the relationship between ε-sensitivity analysis and sensitivity analysis using optimal basis when an ε-optimal solution is sufficiently close to an optimal extreme solution. We show that under primal nondegeneracy or dual nondegeneracy of an optimal extreme solution, the characteristic region of ε-sensitivity analysis converges to that of sensitivity analysis using an optimal basis. However, for the case of both primal and dual degeneracy, we present an example in which the characteristic region of ε-sensitivity analysis is different from that of sensitivity analysis using an optimal basis.