Subscribe Now Subscribe Today
Science Alert
 
Blue
   
Curve Top
Journal of Applied Sciences
  Year: 2009 | Volume: 9 | Issue: 18 | Page No.: 3402-3406
DOI: 10.3923/jas.2009.3402.3406
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Efficient Hybrid Algorithm for Solving Large Scale Constrained Linear Programming Problems

H. Navidi, A. Malek and P. Khosravi

Abstract:
The aim of this study is to find an exact least 2-norm solution to a primal constrained linear programming problem in the standard form. Moreover, we can generate an exact solution to the dual programming problem using the exact least 2-norm solution to the primal problem. The proposed algorithm is suitable for solving linear programming problems with a very large number of variables (105) and a very large number of constraints (106). The exact least 2-norm solution to the primal problem is based on the minimization of exterior penalty functions dual of the dual programming problem. In practice for minimization, we use generalized Newton method and strong wolf conditions in order to find a corresponding suitable step size. This hybrid algorithm converges to the correct optimal solution independent of the values of the given starting point. It is shown that there are some problems that without using strong wolf conditions cannot be solved. The new algorithm can obtain least solution in comparison with MATLAB. Numerical results for a subset of problems from the Netlib collection and a subset of generated large scale linear programs are given. The hybrid algorithm is easy to implement and computationally very efficient. Comparisons are made with available literature.
PDF Fulltext XML References Citation Report Citation
 RELATED ARTICLES:
  •    Numerical Assessment of Path Planning for an Autonomous Robot Passing through Multi-layer Barrier Systems using a Genetic Algorithm
How to cite this article:

H. Navidi, A. Malek and P. Khosravi, 2009. Efficient Hybrid Algorithm for Solving Large Scale Constrained Linear Programming Problems. Journal of Applied Sciences, 9: 3402-3406.

DOI: 10.3923/jas.2009.3402.3406

URL: https://scialert.net/abstract/?doi=jas.2009.3402.3406

COMMENT ON THIS PAPER
 
 
 

 

 
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 

Curve Bottom