Apex Method: A New Scalable Iterative Method for Linear Programming
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 a linear programming problem. The...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/7/1654 |
| _version_ | 1797607516414148608 |
|---|---|
| author | Leonid B. Sokolinsky Irina M. Sokolinskaya |
| author_facet | Leonid B. Sokolinsky Irina M. Sokolinskaya |
| author_sort | Leonid B. Sokolinsky |
| collection | DOAJ |
| description | 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 a linear programming problem. The optimal path refers to a path of the 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. AlsoAdditionally, an algorithm implementing the target stage is given. The convergence of this algorithm is proven. An experimental study of the scalability of the apex method on a cluster computing system is described. The results of applying the apex method to solve problems from the Netlib-LP repository are presented. |
| first_indexed | 2024-03-11T05:31:02Z |
| format | Article |
| id | doaj.art-b2255854333f4291ac5bd7e4bcb47426 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T05:31:02Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-b2255854333f4291ac5bd7e4bcb474262023-11-17T17:08:46ZengMDPI AGMathematics2227-73902023-03-01117165410.3390/math11071654Apex Method: A New Scalable Iterative Method for Linear ProgrammingLeonid B. Sokolinsky0Irina M. Sokolinskaya1School of Electronic Engineering and Computer Science, South Ural State University (National Research University), 76, Lenin Prospekt, 454080 Chelyabinsk, RussiaSchool of Electronic Engineering and Computer Science, South Ural State University (National Research University), 76, Lenin Prospekt, 454080 Chelyabinsk, RussiaThe 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 a linear programming problem. The optimal path refers to a path of the 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. AlsoAdditionally, an algorithm implementing the target stage is given. The convergence of this algorithm is proven. An experimental study of the scalability of the apex method on a cluster computing system is described. The results of applying the apex method to solve problems from the Netlib-LP repository are presented.https://www.mdpi.com/2227-7390/11/7/1654linear programmingapex methoditerative methodprojection-type methodFejér mappingparallel algorithm |
| spellingShingle | Leonid B. Sokolinsky Irina M. Sokolinskaya Apex Method: A New Scalable Iterative Method for Linear Programming Mathematics linear programming apex method iterative method projection-type method Fejér mapping parallel algorithm |
| title | Apex Method: A New Scalable Iterative Method for Linear Programming |
| title_full | Apex Method: A New Scalable Iterative Method for Linear Programming |
| title_fullStr | Apex Method: A New Scalable Iterative Method for Linear Programming |
| title_full_unstemmed | Apex Method: A New Scalable Iterative Method for Linear Programming |
| title_short | Apex Method: A New Scalable Iterative Method for Linear Programming |
| title_sort | apex method a new scalable iterative method for linear programming |
| topic | linear programming apex method iterative method projection-type method Fejér mapping parallel algorithm |
| url | https://www.mdpi.com/2227-7390/11/7/1654 |
| work_keys_str_mv | AT leonidbsokolinsky apexmethodanewscalableiterativemethodforlinearprogramming AT irinamsokolinskaya apexmethodanewscalableiterativemethodforlinearprogramming |