Premium
A new method with hybrid direction for linear programming
Author(s) -
Djeloud Khalil,
Bentobache Mohand,
Bibi Mohand Ouamer
Publication year - 2020
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5836
Subject(s) - simplex algorithm , criss cross algorithm , linear programming , hybrid algorithm (constraint satisfaction) , simplex , algorithm , mathematical optimization , mathematics , point (geometry) , function (biology) , linear fractional programming , computer science , stochastic programming , geometry , evolutionary biology , constraint programming , biology , constraint logic programming
Summary In this work, we propose a new algorithm for solving linear programs. This algorithm starts by an initial support feasible solution, then it moves from one feasible point to a better one following a new hybrid direction. The constructed direction gives a better local improvement of the objective function than the direction of the adaptive method with hybrid direction (AMHD) algorithm proposed in Bibi MO, Bentobache M. A hybrid direction algorithm for solving linear programs. International Journal of Computer Mathematics , 2015; 92(2):200‐216. In order to stop the algorithm, a suboptimality criterion is used and the long step rule is developed for changing the current support. The proposed algorithm is implemented with C++, then a numerical study is conducted on randomly generated test problems and some instances of an optimal control problem. The obtained numerical results show that our algorithm is competitive with AMHD and the primal simplex algorithm of GNU linear programming kit (GLPK).