Ill-posedness with respect to the solvability in linear optimization

We characterize those linear optimization problems that are ill-posed in the sense that arbitrarily small perturbations of the problem’s data may yield both, solvable and unsolvable problems. Thus, the ill-posedness is identified with the boundary of the set of solvable problems. The associated concept of well-posedness turns out to be equivalent to different stability criteria traced out from the literature of linear programming. Our results, established for linear problems with arbitrarily many constraints, also provide a new insight for the ill-posedness in ordinary and conic linear programming. They are formulated in terms of suitable subsets of Rn and Rn+1 (n is the number of unknowns) which only depend on the problem coefficients.This research has been partially supported by grants BFM2002-04114-C02 (01-02) from MCYT (Spain) and FEDER (E.U.), GV04B-648 and GRUPOS04/79 from Generalitat Valenciana (Spain), and Bancaja-UMH (Spain)