Stability of the optimal basis of a linear program under uncertainty (Q2367033)

The article deals with a family of linear programming problems with all the data varying independently of each other within some prescribed tolerances. The stability of the optimal solution of such problems is studied. If \(B\) means an optimal basis then the \(B\)-stable and strongly \(B\)-stable problems are defined. The main result consists in a proof that the optimal basis \(B\) of a linear programming problem remains optimal under variations of all data within prescribed tolerances if and only if a finite subset of explicitly given linear programming problems have the same property. Unfortunately, the cardinality of this subset is exponential in the number of constraints.