Validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911622011813888 |
|---|---|
| author | Awoniyi, Samuel |
| author_facet | Awoniyi, Samuel |
| contents | This article presents a validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem. The proposed algorithm is an implicit reduction procedure that combines primal and dual linear programming problems into a special system of linear equations constrained by complementarity relations and non-negative variables. Each iteration of the algorithm consists of applying a pair of complementary Gauss-Jordan pivoting operations, guided by a necessary-condition lemma. This validation article demonstrates that the proposed algorithm requires no more than 2(k+n) iterations, where k is the number of constraints and n is the number of variables of given general linear programming problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05855 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem Awoniyi, Samuel Optimization and Control 90C05 This article presents a validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem. The proposed algorithm is an implicit reduction procedure that combines primal and dual linear programming problems into a special system of linear equations constrained by complementarity relations and non-negative variables. Each iteration of the algorithm consists of applying a pair of complementary Gauss-Jordan pivoting operations, guided by a necessary-condition lemma. This validation article demonstrates that the proposed algorithm requires no more than 2(k+n) iterations, where k is the number of constraints and n is the number of variables of given general linear programming problem. |
| title | Validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem |
| topic | Optimization and Control 90C05 |
| url | https://arxiv.org/abs/2310.05855 |