A Characterization of Stability in Linear Programming

Abstract

We prove that a necessary and sufficient condition for the primal and dual solution sets of a solvable, finite-dimensional linear programming problem to be stable under small but arbitrary perturbations in the data of the problem is that both of these sets be bounded. The distance from any pair of solutions of the perturbed problem to the solution sets of the original problem is then bounded by a constant multiple of the norm of the perturbations. These results extend earlier work of Williams.