Title: Primal-dual method for a linear program with hybrid direction

Authors: Rima Guerbane; Mohand Ouamer Bibi

Addresses: Research Unit of Modeling and Optimization of Systems (LaMOS), University of Bejaia, Bejaia, 06000, Algeria ' Research Unit of Modeling and Optimization of Systems (LaMOS), University of Bejaia, Bejaia, 06000, Algeria

Abstract: In linear programming, the combination of primal and dual methods is of great importance in the search of efficient resolution algorithms. In the present paper, we are interested to the adaptive method with hybrid direction for the linear programs with bounded variables. After calculating the increment of the dual function with this hybrid direction, an optimality criterion for the dual problem is proved. Using this criterion and the initial speed of change for the dual function, a primal-dual algorithm with hybrid direction is suggested for solving linear programs with bounded variables. In this algorithm, the suboptimality estimate is used as a stopping criterion. A numerical example is presented and to compare the suggested method with three other methods, we have developed an implementation under the MATLAB programming language on randomly generated problems with precision ε ≥ 0, chosen in advance.

Keywords: linear programming; duality; hybrid direction; optimality criteria; primal-dual algorithm; numerical results.

DOI: 10.1504/IJMOR.2022.127383

International Journal of Mathematics in Operational Research, 2022 Vol.23 No.3, pp.316 - 343

Received: 02 Mar 2021
Accepted: 27 Jul 2021
Published online: 01 Dec 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article