A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method

Biressaw C. Wolde () and Torbjörn Larsson ()

Operations Research and Decisions, 2024, vol. 34, issue 2, 163-182

Abstract: 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.

Keywords: linear programming; simplex method; steepest edge; feasible direction; external pivoting (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ord.pwr.edu.pl/assets/papers_archive/ord2024vol34no2_10.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wut:journl:v:34:y:2024:i:2:p:163-182:id:10

DOI: 10.37190/ord2402010

Access Statistics for this article

More articles in Operations Research and Decisions from Wroclaw University of Science and Technology, Faculty of Management Contact information at EDIRC.
Bibliographic data for series maintained by Adam Kasperski ().