×

Intelligent gradient search in linear programming. (English) Zbl 0585.90056

The authors discuss practical aspects and modifications of the polynomial-time algorithm for linear programming by N. Karmarkar [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)]. The method has been tested for small and medium size problems and compares favorably with two other LP codes based on the simplex method.
Reviewer: J.Mandel

MSC:

90C05 Linear programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0557.90065

Software:

XMP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bland, R. G.; Goldfarb, D.; Todd, M. J., the ellipsoid method: A survey, Operations Research, 29, 1039-1091 (1981), Amsterdam · Zbl 0474.90056
[2] Bōhm, K., Lineare Quotientenprogrammierung — Rentabilitātsoptimierung (1978), Haag & Herrchen: Haag & Herrchen Frankfurt/Main
[3] Borgward, K. H., Der durchschnittliche Rechenaufwand beim Simplexverfahren, (Operations Research Proceedings (1984), Springer: Springer Berlin-Heidelberg-New York), 647-660
[4] Dantzig, G. B., Maximization of a linear function of variables subject to linear inequalities, (Koopmans, T. I., Activity Analysis of Production and Allocation (1951)), New York · Zbl 0125.09607
[5] Grötschel, M.; Lovasz, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[6] Hadley, K., Nonlinear and Dynamic Programming (1964), Addison-Wesley Massachusetts: Addison-Wesley Massachusetts Palo Alto, London · Zbl 0179.24601
[7] Hellermann, E.; Rarick, D., Reinversion with the preassigned pivot procedure, Mathematical Programming, 1, 196-216 (1971) · Zbl 0246.65022
[8] Karmarkar, N., A new polynomial-time algorithm for linear programming, (Proceedings of the 16th Annual ACM Symposia on the Theory of Computing. Proceedings of the 16th Annual ACM Symposia on the Theory of Computing, Washington (1984)), 302-310 · Zbl 0557.90065
[9] Khachiyan, L. G., A polynomial algorithm in linear programming, Doklady Akademiia, Novaia Seviia, 244, 5, 1093-1096 (1979), Nauk SSSR · Zbl 0414.90086
[10] Klee, V.; Minty, G. L., How good is the simplex algorithm?, (Shisha, O., Inequalities III (1972), Academic Press: Academic Press New York), 159-179
[11] Krabek, G. B.; Sjoquist, R. J.; Sommer, D. C., The Apex systems past and future technical report; Control Data Corp. 1979, (presented at the TIMS/ORSA Joint National Meeting. presented at the TIMS/ORSA Joint National Meeting, New Orleans, Louisiana (April, 30-May 2, 1979))
[12] Lemke, C. E., The constrained gradient method of linear programming, Journal of the Society for Industrial and Applied Mathematics, 9, 1-17 (1961) · Zbl 0112.12302
[13] Marsten, R. E., The design of the XMP linear programming library, (MIS Technical Report No. 80-2 (1980), Department of Management Information Systems, College of Business and Public Administration, University of Arizona: Department of Management Information Systems, College of Business and Public Administration, University of Arizona Tuscon, Arizona)
[14] Rosen, J. B., The gradient projection method for nonlinear programming, Part I, linear constraints, Journal of the Society for Industrial and Applied Mathematics, 8, 181-217 (1960) · Zbl 0099.36405
[15] Sherali, M. D.; Soyster, A. L.; Baines, S. G., Nonadjacent extreme point methods for solving linear programs, Naval Research Logistics Quarterly, 30, 141-165 (1983) · Zbl 0522.90057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.