|
|
|
A method for solving problems in Linear Programming. This method, invented by G. B. Dantzig in 1947, runs along Edges of the visualization Solid to find the best answer. In 1970, Klee and Minty constructed examples in which the simplex method required an exponential number of steps, but such cases seem never to be encountered in practical applications.
A much more efficient (Polynomial-time) Algorithm was found in 1984 by N. Karmarkar. This method goes through the middle of the Solid and then transforms and warps. It offers many advantages over the simplex method (Nemirovsky and Yudin 1994).
See also Linear Programming
References
Nemirovsky, A. and Yudin, N. Interior-Point Polynomial Methods in Convex Programming. Philadelphia, PA: SIAM, 1994.
Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Downhill Simplex Method in Multidimensions''
and ``Linear Programming and the Simplex Method.''
§10.4 and 10.8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England:
Cambridge University Press, pp. 402-406 and 423-436, 1992.
Tokhomirov, V. M. ``The Evolution of Methods of Convex Optimization.'' Amer. Math. Monthly 103, 65-71, 1996.