Global Pricing and Feasible Directions in Linear Programming

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

A chapter in Operations Research Proceedings 2021, 2022, pp 160-166 from Springer

Abstract: Abstract We present a linear programming approach based on a global pricing function and feasible directions. It is embedded in the framework of the simplex method through the use of external columns, which are combinations of original columns. The global pricing function is composed by the pricing function of the simplex method, which captures the objective’s behaviour over the cone of feasible directions, and an exterior penalty function that captures information about the topology of the entire feasible set. Given a non-degenerate basic feasible solution, a global pricing problem yields a non-edge improving feasible direction, which is translated into an external column that enters the basis. Preliminary computational results indicate that the global pricing principle may have a significant advantage over the ordinary pricing of the simplex method. Further, our new approach allows for several computational strategies, which need to be investigated in future research in order to explore its full potential.

Keywords: Linear program; Pricing; Feasible direction; External pivoting (search for similar items in EconPapers)
Date: 2022
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:lnopch:978-3-031-08623-6_25

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

DOI: 10.1007/978-3-031-08623-6_25

Access Statistics for this chapter

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