Recovering optimal dual solutions in Karmarkar’s polynomial algorithm for linear programming.(English)Zbl 0639.90062
This paper presents a “standard form” variant of Karmarkar’s algorithm for linear programming. The techniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar’s original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.
MSC:
| 90C05 | Linear programming |
| 65K05 | Numerical mathematical programming methods |
| 68Q25 | Analysis of algorithms and problem complexity |
Cite
Full Text:DOI
References:
| [1] | K.M. Anstreicher, ”A monotonic projective algorithm for fractional linear programming”,Algorithmica 1 (1986) 483–498. ·Zbl 0625.90088 ·doi:10.1007/BF01840458 |
| [2] | T.M. Cavalier and A.L. Soyster, ”Some computation experience and a modification of the Karmarkar algorithm”, ISME Working Paper 85-105, Dept. of Industrial and Management Systems Engineering, The Pennsylvania State University (PA, 1985). |
| [3] | G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963). |
| [4] | D.M. Gay, ”A variant of Karmarkar’s linear programming algorithm for problems in standard form”,Mathematical Programming 37 (1987) 81–90. ·Zbl 0629.90056 ·doi:10.1007/BF02591685 |
| [5] | P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, ”On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method”,Mathematical Programming 36 (1986) 183–209. ·Zbl 0624.90062 ·doi:10.1007/BF02592025 |
| [6] | C.C. Gonzaga, ”An algorithm for solving linear programming problems inO(n 3 L) operations”, Memorandum No. UCB/ERL M87/10, Electronic Research Laboratory, University of California, Berkeley (CA, 1987). |
| [7] | M Iri and H. Imai, ”A multiplicative barrier function method for linear programming”,Algorithmica 1 (1986) 455–482. ·Zbl 0641.90048 ·doi:10.1007/BF01840457 |
| [8] | N. Karmarkar, ”A new polynomial-time algorithm for linear programming”, manuscript, Mathematical Science Division, AT&T Bell Laboratories, (NJ, 1984). ·Zbl 0557.90065 |
| [9] | N. Karkarmar, ”A new polynomial-time algorithm for linear programming”,Combinatorica 4 (1984) 373–395. ·Zbl 0557.90065 ·doi:10.1007/BF02579150 |
| [10] | N. Karmarkar, ”Further developments in the new polynomial-time algorithm for linear programming”, Presentation at the12th Mathematical Programming Symposium (Massachusetts Institute of Technology, MA, 1985). |
| [11] | K.O. Kortanek and M. Shi, ”Convergence results and numerical experiments on a linear programming hybrid algorithm”, to appear in theEuropean Journal of Operational Research, Dept. of Mathematics, Carnegie Mellon University (PA, 1985). |
| [12] | I.J. Lustig ”A practical approach to karmarkar’s algorithm”, Technical Report SOL 85-5, Dept. of Operations Research, Stanford University (CA, 1985). |
| [13] | J. Renegar, ”A polynomial-time algorithm, based on Newton’s method, for linear programming”, Report MSRI 07118-86, Mathematical Sciences Research Institute, University of California, Berkeley (CA, 1986). ·Zbl 0654.90050 |
| [14] | M.J. Todd and B.P. Burell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables”,Algorithmica 1 (1986) 409–424. ·Zbl 0621.90048 ·doi:10.1007/BF01840455 |
| [15] | P.M. Vaidya, ”An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations”, manuscript, AT&T Bell Laboratories (NJ, 1987). ·Zbl 0708.90047 |
| [16] | R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”On a modification of Karmarkar’s linear programming algorithm”,Algorithmica 1 (1986) 395–407. ·Zbl 0626.90056 ·doi:10.1007/BF01840454 |
| [17] | Y. Ye, ”K-projection and cutting-objective method for linear programming”, Presentation at the12th Mathematical Programming Symposium (Massachusetts Institute of Technology, MA, 1985). |
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.
