Infoscience

Conference paper

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.

    Note:

    PRO 72.01

    Reference

    • ROSO-CONF-1972-001

    Record created on 2006-02-13, modified on 2016-08-08

Fulltext

  • There is no available fulltext. Please contact the lab or the authors.

Related material