In this paper, we propose a modified centered climbing algorithm (MCCA) for linear programs, which improves the centered climbing algorithm (CCA) developed for linear programs recently. MCCA implements a specific climbing scheme where a violated constraint is probed by means of the centered vector used by CCA. Computational comparison is made with CCA and the simplex method. Numerical tests show that, on average CPU time, MCCA runs faster than both CCA and the simplex method in terms of tested problems. In addition, a simple initialization technique is introduced.
References
[1]
G. B. Dantzig, “Linear Programming and Extensions,” Princeton University Press, Princeton, 1963.
[2]
N. Karmarkar, “A New Polynomial-time Algorithm for Linear Programming,” Combinatorica, Vol. 4, No. 4, 1984, pp. 373-395. doi:10.1145/800057.808695
[3]
K. G. Murty and Y. Fathi, “A Feasible Direction Method for Linear Programming,” Operations Research Letters, Vol. 3, No. 3, 1984, pp. 121-127.
doi:10.1016/0167-6377(84)90003-8
[4]
L. G. Khachian, “A Polynomial Algorithm in Linear Programming,” Soviet Mathematics Doklady, Vol. 20, 1979, pp. 191-194.
[5]
Y. Liu, “An Exterior Point Linear Programming Method Based on Inclusive Normal Cones,” Journal of Industrial and Management Optimization, Vol. 6, No. 4, 2010, pp. 825-846. doi:10.3934/jimo.2010.6.825
[6]
M.-F. Ding, Y. Liu and J. A. Gear, “An Improved Targeted Climbing Algorithm for Linear Programs,” Numerical Algebra, Control and Optimization (NACO), Vol. 1, No. 3, 2011, pp. 399-405. doi:10.3934/naco.2011.1.399
[7]
R. J. Vanderbei, “Linear Programming: Foundations and Extensions,” 3rd Edition, Springer, New York, 2008.
[8]
V. Klee and G. J. Minty, “How Good Is the Simplex Algorithm?” In: O. Shisha, Ed., Inequalities III, Academic Press, New York, 1972, pp. 159-175.
