×

zbMATH — the first resource for mathematics

A monotonic projective algorithm for fractional linear programming. (English) Zbl 0625.90088
The purpose of this paper is to demonstrate that N. Karmarkar’s projective algorithm [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] for linear programming is fundamentally an algorithm for fractional linear programming on the simplex. Convergence of the algorithm is established assuming only an initial lower bound on the optimal objective value using either the lower bound construction proposed by the author [Analysis of a modified Karmarkar algorithm for linear programming, Working Paper, Series B 84, Yale School of Oranization and Management, New Haven, CT, 1985.] or a construction proposed by M. J. Todd and B. P. Burrell [Algorithmica 1, 409-424 (1986; Zbl 0621.90048)]. The author shows that the algorithm can be made monotone and that the monotonic algorithm can be applied to obtain an initial lower bound.

MSC:
90C32 Fractional programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
PDF BibTeX Cite
Full Text: DOI
References:
[1] 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.
[2] M. S. Bazaraa and C. M. Shetty,Nonlinear Programming-Theory and Algorithms, Wiley, New York, 1979. · Zbl 0476.90035
[3] 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.
[4] C. Gonzaga, A conical projection algorithm for linear programming, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1985.
[5] D. Jensen, Private communication, 1986.
[6] N. Karmarkar, A new polynomial-time algorithm for linear programming, Manuscript, Mathematical Sciences Division, AT&T Bell Laboratories, Murray Hill, NJ, 1984. · Zbl 0557.90065
[7] N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica,4 (1984), 373–395. · Zbl 0557.90065
[8] M. Padberg, A different convergence proof of the projective method for linear programming, Manuscript, New York University, New York, 1985.
[9] M. Padberg, Solution of a nonlinear programming problem arising in the projective algorithm for linear programming, Manuscript, New York University, New York, 1985.
[10] 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.
[11] M. J. Todd, Private communication, 1986.
[12] 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. · Zbl 0621.90048
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.