Abstract
We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. M. Anstreicher, Analysis of a modified Karmarkar algorithm for linear programming, Working Paper, Series B #84, Yale School of Organization and Management, New Haven, CT, 1985.
M. S. Bazaraa and C. M. Shetty,Nonlinear Programming-Theory and Algorithms, Wiley, New York, 1979.
D. M. Gay, A variant of Karmarkar's linear programming algorithm for problems in standard form, Manuscript, AT&T Bell Laboratories; Murray Hill, NJ, 1985.
C. Gonzaga, A conical projection algorithm for linear programming, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1985.
D. Jensen, Private communication, 1986.
N. Karmarkar, A new polynomial-time algorithm for linear programming, Manuscript, Mathematical Sciences Division, AT&T Bell Laboratories, Murray Hill, NJ, 1984.
N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica,4 (1984), 373–395.
M. Padberg, A different convergence proof of the projective method for linear programming, Manuscript, New York University, New York, 1985.
M. Padberg, Solution of a nonlinear programming problem arising in the projective algorithm for linear programming, Manuscript, New York University, New York, 1985.
A. E. Steger, An extension of Karmarkar's algorithm for bounded linear programming problems, M.Sc. Thesis, State University of New York, Stony Brook, NY, 1985.
M. J. Todd, Private communication, 1986.
M. J. Todd and B. P. Burrell, An extension of Karmarkar's algorithm for linear programming using dual variables, Technical Report No. 648, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1985.
Author information
Authors and Affiliations
Additional information
Communicated by Nimrod Megiddo.
Rights and permissions
About this article
Cite this article
Anstreicher, K.M. A monotonic projective algorithm for fractional linear programming. Algorithmica 1, 483–498 (1986). https://doi.org/10.1007/BF01840458
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01840458