# zbMATH — the first resource for mathematics

On lower bound updates in primal potential reduction methods for linear programming. (English) Zbl 0754.90034
From the abstract: “We present a procedure for computing lower bounds for the optimal cost in a linear programming problem. Although no projective transformations or problem restatements are used, the method coincides with the procedures by M. J. Todd and B. P. Burrell [Algorithmica 1, 409-424 (1986; Zbl 0621.90048)] and by G. de Ghellink and J.-Ph. Vial [Math. Program. 39, 79-92 (1987; Zbl 0636.90054)] when these procedures are applicable.

##### MSC:
 90C05 Linear programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text:
##### References:
 [1] K. Anstreicher, ”A monotonic projective algorithm for fractional linear programming,”Algorithmica 1 (1986) 483–498. · Zbl 0625.90088 [2] K. Anstreicher and R. Bosch, ”Long steps in a O(n 3 L) algorithm for linear programming,” to appear in:Mathematical Programming (1992). · Zbl 0783.90066 [3] R.M. Freund, ”Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function,”Mathematical Programming 51 (1991) 203–222. · Zbl 0743.90073 [4] G. de Chellinck and J.-P. Vial, ”A polynomial Newton method for linear programming,”Algorithmica 1 (1986) 425–453. · Zbl 0629.90058 [5] C. Gonzaga, ”Conical projection algorithms for linear programming,”Mathematical Programming 43 (1988) 151–173. · Zbl 0667.90064 [6] C. Gonzaga, ”Large-steps path-following algorithms for linear programming: Potential reduction method,” Internal Report, COPPE – Federal University of Rio de Janeiro (Rio de Janeiro, Brasil, 1989). [7] C. Gonzaga, ”Polynomial affine algorithms for linear programming,”Mathematical Programming 49 (1991) 7–21. · Zbl 0777.90027 [8] C. Gonzaga, ”Search directions for interior linear programming methods,”Algorithmica 6 (1991) 153–181. · Zbl 0718.90064 [9] C. Gonzaga and M.J. Todd, ”An $$O(\sqrt n L)$$ -iteration large-step primal–dual affine algorithm for linear programming,” Technical Report 862, School of Operations Research and Industrial Engineering, Cornell University, (Ithaca, NY, 1989). · Zbl 0783.90071 [10] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 [11] M. Kojima, S. Mizuno, and A. Yoshise, ”An $$O(\sqrt n L)$$ iteration potential reduction algorithm for linear complementarity problems,”Mathematical Programming 50 (1991) 331–342. · Zbl 0738.90077 [12] M. Kojima and Y. Ye. ”Recovering optimal dual solutions in Karmarkar’s polynomial algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317. · Zbl 0639.90062 [13] A. Steger, ”An extension of Karmarkar’s algorithm for bounded linear programming problems,” Master’s Thesis, SUNY at Stonybrook (Stonybrook, NY, 1985). [14] M. Todd and B. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424. · Zbl 0621.90048 [15] M.J. Todd, ”The effects of sparsity, degeneracy, and null and unbounded variables in variants of Karmarkar’s linear programming algorithm,” Technical Report 857, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1989). [16] M.J. Todd and Y. Wang, ”On combined phase 1-phase 2 projective methods for linear programming,” Technical Report 877, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1989). [17] M.J. Todd and Y. Ye, ”A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529. · Zbl 0722.90044 [18] J.-P. Vial, ”A unified approach to projective algorithms for linear programming,” in: Dolecki, ed., (Springer, Berlin, 1989). · Zbl 0683.90046 [19] Y. Ye, ”An O(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258. · Zbl 0734.90057 [20] Y. Ye, ”A class of projective transformations for linear programming,” to appear in:SIAM Journal on Computing (1991). [21] Y. Ye, ”Line search in potential reduction algorithms for linear programming,” Manuscript, Department of Management Sciences, The University of Iowa (Iowa City, IA, 1989). [22] Y. Ye, ”Practical approaches to potential function method for linear programming,” Manuscript, Integrated Systems Inc. (Santa Clara, CA, 1989).
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.