Distance to Solvability/Unsolvability in Linear Optimization

In this paper we measure how much a linear optimization problem, in Rn, has to be perturbed in order to lose either its solvability (i.e., the existence of optimal solutions) or its unsolvability property. In other words, if we consider as ill-posed those problems in the boundary of the set of solvable ones, then we can say that this paper deals with the associated distance to ill-posedness. Our parameter space is the set of all the linear semi-infinite programming problems with a fixed, but arbitrary, index set. In this framework, which includes as a particular case the ordinary linear programming, we obtain a formula for the distance from a solvable problem to unsolvability in terms of the nominal problem's coefficients. Moreover, this formula also provides the exact expression, or a lower bound, of the distance from an unsolvable problem to solvability. The relationship between the solvability and the primal-dual consistency is analyzed in the semi-infinite context, underlining the differences with the finite case.This research has been partially supported by grants BFM2002-04114-C02 (01-02) from MCYT (Spain) and FEDER (E.U.), and GV04B-648 and GRUPOS04/79 from Generalitat Valenciana (Spain)