A variant of Karmarkar’s linear programming algorithm for problems in standard form.(English)Zbl 0629.90056
A variant of Karmarkar’s LP algorithm is presented. This algorithm works only with problems in standard form and requires no a priori information about the objective function value. The algorithm produces sequences of primal and dual feasible solutions whose objective values converge to the optimal objective function value. The only restrictive assumption is that the feasible region is bounded with nonempty interior. Compactness of the feasible region can be relaxed to compactness of the set of optimal solutions.
Reviewer: J.Ramik
Cite
Full Text:DOI
References:
| [1] | K. Anstreicher, ”A monotonic projective algorithm for fractional linear programming”, manuscript, School of Organization and Management Yale University (March 1986). ·Zbl 0625.90088 |
| [2] | J.E. Dennis, Jr., A.M. Morshedi and K. Turner. ”A variable metric variant of the Karmarkar algorithm for linear programming,” Technical Report 86-13, Department of Mathematical Sciences, Rice University, June 1986. ·Zbl 0635.90058 |
| [3] | D. Goldfarb and S. Mehrotra, ”A relaxed version of Karmarkar’s method,” manuscript, School of Engineering and Applied Science, Columbia University (December 1985). ·Zbl 0654.90049 |
| [4] | C. Gonzaga, ”A conical projection algorithm for linear programming,” Memorandum UCB/ERL M85/61, Department of Electrical Engineering and Computer Science, University of California, Berkeley (July 1985). |
| [5] | N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. ·Zbl 0557.90065 ·doi:10.1007/BF02579150 |
| [6] | I.J. Lustig, ”A practical approach, to Kramarkar’s algorithm,” Technical Report SOL 85-5, Systems Optimization Laboratory, Department of Operations Research Stanford University (June 1985). |
| [7] | A.E. Steger, ”An extension of Karmarkar’s algorithm for bounded linear programming problems,” M.S. thesis, State University of New York at Stony Brook (August 1985). |
| [8] | M. J. Todd and B. P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,” Technical Report 648, School of Operations Research and Industrial Engineering, Cornell University (January 1985). ·Zbl 0621.90048 |
| [9] | J.A. Tomlin, ”An experimental approach to Karmarkar’s projective method for linear programming,” manuscript, Ketron Incorporated (January 1985). ·Zbl 0634.90044 |
| [10] | Y. Ye., ”Cutting objective and scaling methods–A ’simple’ polynomial algorithm for linear programming,” manuscript, Engineering-Economic Systems Department, Stanford University (August 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.
