A new method with hybrid direction for linear programming. (11th June 2020)

• Record Type: Journal Article
• Authors: Djeloud, Khalil; Bentobache, Mohand; Bibi, Mohand Ouamer
• Other Names: Schifanella Claudio guestEditor.; Bracciali Andrea guestEditor.; Benkrid Soumia guestEditor.; Moussa Rim guestEditor.; Badir Hassan guestEditor.; Lo Moussa guestEditor.; Bellatreche Ladjel guestEditor.
• Is Part Of: Concurrency and computation. Volume 33:Number 1(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-06-11
• Subjects: hybrid direction -- linear programming -- long step rule -- numerical experiments -- open‐source solver GLPK -- suboptimality estimate; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5836
• Languages: English
• ISSNs: 1532-0626

Abstract

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).