Advanced Search
Article Contents
Article Contents

An improved targeted climbing algorithm for linear programs

Abstract Related Papers Cited by
  • A class of exterior climbing algorithms (ladder algorithms) has been developed recently. Among this class, the targeted climbing algorithm has demonstrated very good numerical performance. In this paper an improved targeted climbing linear programming algorithm is proposed. A sequence of changing reference points, instead of a fixed reference point as in the original algorithm, is used in the improved algorithm to speed up the convergence. The improved algorithm is especially suited to solve problems involving many constraints close to the optimal solution---the case that causes many algorithms to slow down dramatically. Numerical tests and comparison with the simplex methods are presented. Our results show that the current algorithm works better on average than the simplex methods and is much faster for a large class of problems.
    Mathematics Subject Classification: Primary: 90C05; Secondary: 49M30.


    \begin{equation} \\ \end{equation}
  • [1]

    H. Arsham, A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs, Applied Mathematics and Computation, 188 (2007), 596-611.


    H. Arsham, T. Damij and J. Grad, An algorithm for simplex tableau reduction: the push-to-pull solution strategy, Applied Mathematics and Computation, 137 (2003), 525-547.


    E. Barnes, V. Chen, B. Gopalakrishnan and E. L. Johnson, A least-squares primal-dual algorithm for solving linear programming problems, Operations Research Letters, 30 (2002), 289-294.doi: 10.1016/S0167-6377(02)00163-3.


    G. B. Dantzig, "Linear Programming and Extensions," Princeton University Press, Princeton, N. J., 1963.


    N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.doi: 10.1007/BF02579150.


    Y. Liu, An exterior point linear programming method based on inclusive normal cones, Journal of Industrial and Management Optimization, 6 (2010), 825-846.doi: 10.3934/jimo.2010.6.825.


    P. Q. Pan, A largest-distance pivot rule for the simplex algorithm, European Journal of Operational Research, 187 (2008), 393-402.


    X. J. Xu and Y. Y. Ye, A generalized homogeneous and self-dual algorithm for linear programming, Operations Research Letters, 17 (1995), 181-190.doi: 10.1016/0167-6377(95)00002-2.


    W. C. Yeh and H. W. Corley, A simple direct cosine simplex algorithm, Applied Mathematics and Computation, 214 (2009), 178-186.doi: 10.1016/j.amc.2009.03.080.

  • 加载中

Article Metrics

HTML views() PDF downloads(78) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint