A Steepest Feasible Direction Extension of the Simplex Method

Biressaw C. Wolde () and Torbjörn Larsson ()
Additional contact information
Biressaw C. Wolde: Linköping University
Torbjörn Larsson: Linköping University

A chapter in Operations Research Proceedings 2019, 2020, pp 113-121 from Springer

Abstract: Abstract We present a feasible direction approach to general linear programming, which can be embedded in the simplex method although it works with non-edge feasible directions. The feasible direction used is the steepest in the space of all variables, or an approximation thereof. Given a basic feasible solution, the problem of finding a (near-)steepest feasible direction is stated as a strictly convex quadratic program in the space of the non-basic variables and with only non-negativity restrictions. The direction found is converted into an auxiliary non-basic column, known as an external column. Our feasible direction approach allows several computational strategies. First, one may choose how frequently external columns are created. Secondly, one may choose how accurately the direction-finding quadratic problem is solved. Thirdly, near-steepest directions can be obtained from low-dimensional restrictions of the direction-finding quadratic program or by the use of approximate algorithms for this program.

Keywords: Linear program; Steepest-edge; Feasible direction; External pivoting (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-030-48439-2_14

Ordering information: This item can be ordered from
http://www.springer.com/9783030484392

DOI: 10.1007/978-3-030-48439-2_14

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().