We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
PROBABILISTIC MODELS FOR LINEAR PROGRAMMING.
- Authors
Todd, Michael J.
- Abstract
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.
- Subjects
LINEAR programming; PROBABILISTIC number theory; PROBABILITY theory; MATHEMATICAL variables; RANDOM variables; OPERATIONS research; ALGORITHMS; DISTRIBUTION (Probability theory); MATHEMATICAL programming; COMPUTER algorithms
- Publication
Mathematics of Operations Research, 1991, Vol 16, Issue 4, p671
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.16.4.671