American Institute of Mathematical Sciences

Advanced
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

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 & 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. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/S0167-6377(02)00163-3. Google Scholar

[4]

G. B. Dantzig, "Linear Programming and Extensions,", Princeton University Press, (1963). Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

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. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/S0167-6377(02)00163-3. Google Scholar

[4]

G. B. Dantzig, "Linear Programming and Extensions,", Princeton University Press, (1963). Google Scholar

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[1]

Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & 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 & 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 & 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 & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[5]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142
[6]

Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 979-987. doi: 10.3934/dcdss.2019066
[7]

Honggang Yu. An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-914. doi: 10.3934/dcdss.2019060
[8]

Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019018
[9]

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 & Continuous Dynamical Systems - B, 2013, 18 (4) : 1031-1051. doi: 10.3934/dcdsb.2013.18.1031
[10]

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
[11]

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
[12]

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 & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[13]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[14]

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 & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200
[15]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097
[16]

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 & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[17]

Xiaojun Zhou, Chunhua Yang, Weihua Gui. State transition algorithm. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1039-1056. doi: 10.3934/jimo.2012.8.1039
[18]

Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics & Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005
[19]

José A. Cañizo, Alexis Molino. Improved energy methods for nonlocal diffusion problems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1405-1425. doi: 10.3934/dcds.2018057
[20]

François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 261-310. doi: 10.3934/dcds.2004.11.261

 Impact Factor: 

Tools

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences