Geodesic
On new version of the apex method for solving linear programming problems
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 12 (2023) no. 2, pp. 5-46

Voir la notice de l'article provenant de la source Math-Net.Ru

The article presents a new scalable iterative method for linear programming, called the apex method. The key feature of this method is constructing a path close to optimal on the surface of the feasible region from a certain starting point to the exact solution of the linear programming problem. The optimal path refers to a path of minimum length according to the Euclidean metric. The apex method is based on the predictor-corrector framework and proceeds in two stages: Quest (predictor) and Target (corrector). The Quest stage calculates a rough initial approximation of the linear programming problem. The Target stage refines the initial approximation with a given precision. The main operation used in the apex method is an operation that calculates the pseudoprojection, which is a generalization of the metric projection to a convex closed set. This operation is used both in the Quest stage and in the Target stage. A parallel algorithm using a Fejér mapping to compute the pseudoprojection is presented. An analytical estimation of the parallelism degree of this algorithm is obtained. Also, an algorithm implementing the Target stage is given. The convergence of this algorithm is proven. The results of applying the apex method for solving various linear programming problems are presented.
Keywords: linear programming, apex method, iterative method, projection-type method, Fejér mapping, parallel algorithm, scalability evaluation. 
@article{VYURV_2023_12_2_a0,
     author = {L. B. Sokolinsky and I. M. Sokolinskaya},
     title = {On new version of the apex method for solving linear programming problems},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {5--46},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2023_12_2_a0/}
}
TY  - JOUR
AU  - L. B. Sokolinsky
AU  - I. M. Sokolinskaya
TI  - On new version of the apex method for solving linear programming problems
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2023
SP  - 5
EP  - 46
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURV_2023_12_2_a0/
LA  - ru
ID  - VYURV_2023_12_2_a0
ER  - 
%0 Journal Article
%A L. B. Sokolinsky
%A I. M. Sokolinskaya
%T On new version of the apex method for solving linear programming problems
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2023
%P 5-46
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURV_2023_12_2_a0/
%G ru
%F VYURV_2023_12_2_a0
L. B. Sokolinsky; I. M. Sokolinskaya. On new version of the apex method for solving linear programming problems. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 12 (2023) no. 2, pp. 5-46. http://geodesic.mathdoc.fr/item/VYURV_2023_12_2_a0/