Mathematics of Operations Research November 1991 [antikvár]

MATHEMATICS OF OPERATIONS RESEARCH Vol. 16, No. 4, November 1991 Prmted in U.S.A. PROBABILISTIC MODELS FOR LINEAR PROGRAMMING* MICHAEL J. TODD'^ We propose and investigate new probabilistic models for linear programming. In contrast to previous models, ours guarantee the existence of optimal solutions and are symmetric under duality. While in some respects our 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 or throughout the feasible region using null variables. Moreover, the precision of the distributions allows us to compute the probability that the feasible region 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 we also introduce a model for generating random linear programming problems on a simplex. 1. Introduction. There have been many probabilistic models suggested for generating random polyhedra or random linear programming problems. The concern in geometric probability (see Efron [12], Raynaud [22], Renyi and Sulanke [23] and W. Schmidt [26]) has generally been in the asymptotic number of extreme points and facets of the convex hull of a collection of randomly generated points. By taking polars, these results concern the asymptotic number of facets and vertices of polyhedra defined by a collection of randomly generated inequalities. In the mathematical programming literature, the first paper appears to have been by Motzkin [20], who computed the probability of feasibility of a system of inequalities each of which could have either sense with equal probability independently. This was the first appearance of the sign-invariant model, which was later studied by Prekopa [21] and then extensively in the eighties by Adler and Berenguer [2, 3] and May and Smith [18]. This research culminated in results on the expected length of paths of a parametric algorithm by Haimovich [13] and Adler [1] and of a complete 2-phase algorithm by Adler, Karp and Shamir [4], Adler and Megiddo [5], and Todd [30]. The sign-invariant models comes in two flavors: unconditional, as studied by Motzkin, Prekopa, and the last three papers [4, 5, 30]; and conditional on the nonemptiness of the feasible region or of the efficient path in [1, 2, 3, 13, 18]. It is unfortunate that the strongest results, with a quadratic bound on the expected number of steps for a complete 2-phase algorithm, require a distribution that generates infeasible or unbounded problems with probabilities approaching one as the dimension increases. Only in the case where the number of inequalities is twice the dimension can one easily remedy this defect, at the cost of increasing the exponent in the bound to 5/2. Another sign-invariant model was that considered in Smale's work [27]. This model was later considerably generalized by Smale [28] and Blair [6]. •Received February 22, 1989; revised April II, 1990. AMS 1980 subject classification. Primary: 90C05; Secondary: 90CI5. lAOR 1973 subject classification. Main: Programming: Linear; Cross references: Programming; Probabilistic. OR/MS Index 1978 subject classification. Primary: 650 Programming/Linear/Theory 663: Programming/Nonlinear/Stochastic. Key words. Linear Programming, probabilistic models, Karmarkar's algorithm, Gaussian distributions. *This work was partially supported by NSF Grant ECS-8602534 and ONR Contract N000I4-87-K-02I2. 671