Probabilistic models for linear programming

The paper proposes and investigates new probabilistic models for linear programming. In contrast to previous models, the present ones guarantee the existence of optimal solutions and are symmetric under duality. While in some respects the distributions are very special, there is sufficient flexibility to permit an arbitrary degree of primal and/or dual degeneracy, either just at the optimal solution throughout the feasible region using null variables. Moreover, the precision of the distributions allows the computation of the probability that the feasible rgion is bounded as well as the distribution of the distance to a constraint hyperplane and that of the components of a vertex. Interest in these measures stems from Karmarkar’s algorithm, and a model for generating random linear programming problems on a simplex is also introduced.