IDEAS home Printed from https://ideas.repec.org/a/wut/journl/v34y2024i2p163-182id10.html
   My bibliography  Save this article

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

Author

Listed:
  • Biressaw C. Wolde
  • Torbjörn Larsson

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.

Suggested Citation

  • Biressaw C. Wolde & Torbjörn Larsson, 2024. "A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 34(2), pages 163-182.
    • Handle: RePEc:wut:journl:v:34:y:2024:i:2:p:163-182:id:10
    DOI: 10.37190/ord2402010
    as

    Download full text from publisher

    File URL: https://ord.pwr.edu.pl/assets/papers_archive/ord2024vol34no2_10.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.37190/ord2402010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. H.A. Eiselt & C.‐L. Sandblom, 1985. "External Pivoting In The Simplex Algorithm," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 39(4), pages 327-341, December.
    2. Karl Heinz Borgwardt & Petra Huhn, 1999. "A lower bound on the average number of Pivot-steps for solving linear programs Valid for all variants of the Simplex-Algorithm," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(2), pages 175-210, April.
    3. Fathi, Yahya & Murty, Katta G., 1989. "Computational behavior of a feasible direction method for linear programming," European Journal of Operational Research, Elsevier, vol. 40(3), pages 322-328, June.
    4. Fukuda, K. & Terlaky, T., 1999. "On the existence of a short admissible pivot sequence for feasibility and linear optimization problems," Pure Mathematics and Applications, Department of Mathematics, Corvinus University of Budapest, vol. 10(4), pages 431-447.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. David Avis & Bohdan Kaluzny, 2008. "Computing monotone disjoint paths on polytopes," Journal of Combinatorial Optimization, Springer, vol. 16(4), pages 328-343, November.
    2. Rönnberg, Elina & Larsson, Torbjörn, 2014. "All-integer column generation for set partitioning: Basic principles and extensions," European Journal of Operational Research, Elsevier, vol. 233(3), pages 529-538.
    3. Konstantinos Paparrizos & Nikolaos Samaras & Angelo Sifaleras, 2015. "Exterior point simplex-type algorithms for linear and network optimization problems," Annals of Operations Research, Springer, vol. 229(1), pages 607-633, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wut:journl:v:34:y:2024:i:2:p:163-182:id:10. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Adam Kasperski (email available below). General contact details of provider: https://edirc.repec.org/data/iopwrpl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.