An improved targeted climbing algorithm for linear programs

Mingfang Ding; Yanqun Liu; John Anthony Gear

doi:10.3934/naco.2011.1.399

Article Contents

2011, Volume 1, Issue 3: 399-405. Doi: 10.3934/naco.2011.1.399

This issue Previous Article Finding all minimal elements of a finite partially ordered set by genetic algorithm with a prescribed probability Next Article On linear vector optimization duality in infinite-dimensional spaces

An improved targeted climbing algorithm for linear programs

1.
School of Mathematical & Geospatial Sciences, RMIT University, Melbourne

Received: May 2011

Revised: July 2011

Published: August 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C05; Secondary: 49M30.

Citation:

Related Papers

Cited by

References

[1]	H. Arsham, A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs, Applied Mathematics and Computation, 188 (2007), 596-611.
[2]	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.
[3]	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.
[4]	G. B. Dantzig, "Linear Programming and Extensions," Princeton University Press, Princeton, N. J., 1963.
[5]	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.doi: 10.1007/BF02579150.
[6]	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.
[7]	P. Q. Pan, A largest-distance pivot rule for the simplex algorithm, European Journal of Operational Research, 187 (2008), 393-402.
[8]	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.
[9]	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.