A hybrid direction algorithm for solving linear programs

Abstract

In this paper we suggest a new ascent direction for the adaptive method developed by Gabasov et al. (A method of solving general linear programming problems, Doklady AN BSSR 23(3) (1979), pp. 197–200 (in Russian)) for solving linear programs with bounded variables. A quantity called optimality estimate is defined, necessary and sufficient conditions of optimality based on this estimate are derived. An algorithm called the adaptive method with hybrid direction (AMHD) is suggested and a numerical example is given for illustration purpose. In order to compare the suggested algorithm with the classical primal simplex algorithm employing Dantzig's rule (PSA), we have developed a numerical implementation under the MATLAB programming language. The experimental study involves the CPU time and the iterations number of the two algorithms applied to solve randomly generated test problems of different dimensions. It has been shown that when the problem dimension increases, the superiority of AMHD over primal simplex algorithm increases.

Keywords:

• linear programming
• adaptive method
• hybrid direction
• optimality estimate
• computational experiments

2000 AMS Subject Classification::

• 90C05

Acknowledgements

The authors are indebted to the Editor-in-Chief Dr Qin Sheng and to the anonymous referees whose comments and suggestions have improved the quality of this paper.