An improved targeted climbing algorithm for linear programs

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

2011, 1(3): 399-405. doi: 10.3934/naco.2011.1.399

An improved targeted climbing algorithm for linear programs

Mingfang Ding ^1, , Yanqun Liu ^1, and John Anthony Gear ^1,

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

Received May 2011 Revised July 2011 Published September 2011

Abstract
Related Papers

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: Improved targeted climbing algorithm, simplex methods., original targeted climbing algorithm.

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

Citation: Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399

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.

show all references

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.

[1]	Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial and Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251
[2]	Chloe A. Fletcher, Jason S. Howell. Dynamic modeling of nontargeted and targeted advertising strategies in an oligopoly. Journal of Dynamics and Games, 2017, 4 (2) : 97-124. doi: 10.3934/jdg.2017007
[3]	I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[4]	Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[5]	Xiao-Wen Chang, David Titley-Peloquin. An improved algorithm for generalized least squares estimation. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 451-461. doi: 10.3934/naco.2020044
[6]	Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[7]	Seigan Hayashi, Chris J. Cameron, Stefanie Gutschmidt. A novel sensing concept utilizing targeted, complex, nonlinear MEMS dynamics. Journal of Computational Dynamics, 2022 doi: 10.3934/jcd.2022012
[8]	Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1571-1584. doi: 10.3934/jimo.2019018
[9]	Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 979-987. doi: 10.3934/dcdss.2019066
[10]	Ouafa Belguidoum, Hassina Grar. An improved projection algorithm for variational inequality problem with multivalued mapping. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022002
[11]	Urszula Ledzewicz, Mozhdeh Sadat Faraji Mosalman, Heinz Schättler. Optimal controls for a mathematical model of tumor-immune interactions under targeted chemotherapy with immune boost. Discrete and Continuous Dynamical Systems - B, 2013, 18 (4) : 1031-1051. doi: 10.3934/dcdsb.2013.18.1031
[12]	Urszula Ledzewicz, Omeiza Olumoye, Heinz Schättler. On optimal chemotherapy with a strongly targeted agent for a model of tumor-immune system interactions with generalized logistic growth. Mathematical Biosciences & Engineering, 2013, 10 (3) : 787-802. doi: 10.3934/mbe.2013.10.787
[13]	Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097
[14]	Junjie Peng, Ning Chen, Jiayang Dai, Weihua Gui. A goethite process modeling method by Asynchronous Fuzzy Cognitive Network based on an improved constrained chicken swarm optimization algorithm. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1269-1287. doi: 10.3934/jimo.2020021
[15]	Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[16]	Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[17]	Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038
[18]	Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[19]	Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060
[20]	Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Mingfang Ding Yanqun Liu John Anthony Gear
on Google Scholar
Mingfang Ding Yanqun Liu John Anthony Gear

[Back to Top]