Research ArticleOpen AccessGoogle Scholar indexed
A Modified Centered Climbing Algorithm for Linear Programming
School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
- 1 School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
- 2 School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
- 3 School of Mathematical & Geospatial Sciences, RMIT University, Melbourne, Australia
Applied Mathematics·Volume 03 (2012)·Pages 1423–1429·Published 31 October 2012·DOI10.4236/am.2012.330200
Copy link · social · email
Abstract
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.
KeywordsLinear ProgrammingLadder MethodClimbing RulesSimplex Method
- G. B. Dantzig, “Linear Programming and Extensions,” Princeton University Press, Princeton, 1963.
- N. Karmarkar, “A New Polynomial-time Algorithm for Linear Programming,” Combinatorica, Vol. 4, No. 4, 1984, pp. 373-395. doi:10.1145/800057.808695
- 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
- L. G. Khachian, “A Polynomial Algorithm in Linear Programming,” Soviet Mathematics Doklady, Vol. 20, 1979, pp. 191-194.
- 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
- 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
- R. J. Vanderbei, “Linear Programming: Foundations and Extensions,” 3rd Edition, Springer, New York, 2008.
- 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.