Ill-posedness with respect to the solvability in linear optimization

AbstractWe 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