On the number of iterations of the simplex method.

RENYI and SULANKE studied the properties of the convex hull of a set of points thrown at random independently of each other. Carnal generalized their results concerning the asymptotic behaviour of the number of faces of that convex hull as the number of points increases. The present work connects those results with the mean number of pivot steps used by the Simplex Method to solve certain Linear Programming Problems. This is made possible through the polar interpretation of the LP-Problems. Monte Carlo Simulation confirmed the results. Aside from statistical applications, it is felt that this kind of an approach will make it possible to characterize optimization problems with polyhedral feasible sets as to their benevolence.


Published in:
Methods of operations research, 2, 248-264
Year:
1972
Publisher:
Verlag Anton Hain
Note:
PRO 72.01
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)