A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method
A feasible direction method for linear programming has been proposed. The method is embedded in the framework of the simplex method, even though it works with non-edge feasible directions. The direction used is the steepest in the space of all variables or an approximation thereof, and it is found b...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wrocław University of Science and Technology
2024-01-01
|
| Series: | Operations Research and Decisions |
| Online Access: | https://ord.pwr.edu.pl/assets/papers_archive/ord2024vol34no2_10.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849429941198782464 |
|---|---|
| author | Biressaw C. Wolde Torbjörn Larsson |
| author_facet | Biressaw C. Wolde Torbjörn Larsson |
| author_sort | Biressaw C. Wolde |
| collection | DOAJ |
| description | A feasible direction method for linear programming has been proposed. The method is embedded in the framework of the simplex method, even though it works with non-edge feasible directions. The direction used is the steepest in the space of all variables or an approximation thereof, and it is found by solving a strictly convex quadratic program in the space of the nonbasic variables. Further, this program guarantees the feasibility of the direction even in the case of degeneracy. To remain within the simplex framework, the direction is represented by an auxiliary, or external, nonbasic column, which is a nonnegative linear combination of original nonbasic columns. We have made an experimental evaluation of the suggested method on both nondegenerate and highly degenerate problem instances. The overall results are very promising for continued research along this line, especially concerning various computational strategies that can be applied when the method is implemented. (original abstract) |
| format | Article |
| id | doaj-art-42e0592738f74b82bbc7061334658b61 |
| institution | Kabale University |
| issn | 2081-8858 2391-6060 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Wrocław University of Science and Technology |
| record_format | Article |
| series | Operations Research and Decisions |
| spelling | doaj-art-42e0592738f74b82bbc7061334658b612025-08-20T03:28:10ZengWrocław University of Science and TechnologyOperations Research and Decisions2081-88582391-60602024-01-01vol. 34no. 2163182171694137A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex MethodBiressaw C. Wolde0Torbjörn Larsson1Linköping University, SwedenLinköping University, SwedenA feasible direction method for linear programming has been proposed. The method is embedded in the framework of the simplex method, even though it works with non-edge feasible directions. The direction used is the steepest in the space of all variables or an approximation thereof, and it is found by solving a strictly convex quadratic program in the space of the nonbasic variables. Further, this program guarantees the feasibility of the direction even in the case of degeneracy. To remain within the simplex framework, the direction is represented by an auxiliary, or external, nonbasic column, which is a nonnegative linear combination of original nonbasic columns. We have made an experimental evaluation of the suggested method on both nondegenerate and highly degenerate problem instances. The overall results are very promising for continued research along this line, especially concerning various computational strategies that can be applied when the method is implemented. (original abstract)https://ord.pwr.edu.pl/assets/papers_archive/ord2024vol34no2_10.pdf |
| spellingShingle | Biressaw C. Wolde Torbjörn Larsson A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method Operations Research and Decisions |
| title | A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method |
| title_full | A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method |
| title_fullStr | A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method |
| title_full_unstemmed | A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method |
| title_short | A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method |
| title_sort | steepest feasible direction method for linear programming derivation and embedding in the simplex method |
| url | https://ord.pwr.edu.pl/assets/papers_archive/ord2024vol34no2_10.pdf |
| work_keys_str_mv | AT biressawcwolde asteepestfeasibledirectionmethodforlinearprogrammingderivationandembeddinginthesimplexmethod AT torbjornlarsson asteepestfeasibledirectionmethodforlinearprogrammingderivationandembeddinginthesimplexmethod AT biressawcwolde steepestfeasibledirectionmethodforlinearprogrammingderivationandembeddinginthesimplexmethod AT torbjornlarsson steepestfeasibledirectionmethodforlinearprogrammingderivationandembeddinginthesimplexmethod |