EUVIMEDEUVIMED entdecken
Crossref

A global pricing extension of the simplex method

Biressaw Chali Wolde, Torbjörn Larsson

Operations Research and Decisions · 2025

DOI: 10.37190/ord/211685 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Operations Research and Decisions, 2025. Verfasst von Biressaw Chali Wolde und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce the use of a global, nonlinear price function in linear programming and the simplex method. The usual, linear price function of this method captures the objective’s behaviour over the cone of directions defined by the nonbasic columns, whereas the global price function adds information about the topology of the whole feasible set. This is achieved by using an exterior penalty function. Further, degeneracy is effectively handled through explicit degeneracy-breaking constraints. The use of the global price function leads to a pricing problem that yields an improving, non-edge feasible direction, which is converted to an auxiliary variable to be used in the simplex method. Preliminary computational results with nondegenerate and highly degenerate linear programs show that the introduction of a global price function in the simplex method, and degeneracy-breaking constraints if needed, may significantly enhance its performance.

Zitieren

APA

Wolde, B. C., & Larsson, T. (2025). A global pricing extension of the simplex method. Operations Research and Decisions. https://doi.org/10.37190/ord/211685

Vancouver

Wolde BC, Larsson T. A global pricing extension of the simplex method. Operations Research and Decisions. 2025. doi:10.37190/ord/211685

BibTeX
@article{Wolde2025,
  author = {Wolde, Biressaw Chali and Larsson, Torbjörn},
  title = {A global pricing extension of the simplex method},
  journal = {Operations Research and Decisions},
  year = {2025},
  doi = {10.37190/ord/211685}
}
Kostenlos starten →