Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems

Blien Filez, Csizmadia Zsolt, Tibor Illes

Research output: Book/ReportScholarly edition

3 Citations (Scopus)

Abstract

We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by m∆, where ∆ is a constant determined by the input data of the problem and m is the number of constraints. The constant ∆ cannot be bounded in general by a polynomial of the bit length of the input data. Realizing an interesting property of degeneracy led us to construct a new recursive procedure to handle degenerate problems. The essence of this procedure is as follows. If a degenerate pivot tableau is obtained, we define a smaller problem, restricting the pivot position to a smaller part of the tableau. On this smaller problem, we follow the same principles as before to choose the pivot position. The smaller problem is either solved completely or a new degenerate subproblem is identified. If the subproblem was solved then we return to the starting larger problem, where either we can make a nondegenerate pivot, or detect that the problem is infeasible. It is easy to see that the maximum depth of the recursively embedded subproblems is smaller than 2 m. Upper bounds for the complexities of linear programming version of MBU and the first phase of the simplex algorithm can be found similarly under the nondegeneracy assumption.
Original languageEnglish
Place of PublicationBudapest
Number of pages25
Volume2005
Publication statusPublished - May 2005

Publication series

NameOperations Research Report
PublisherEötvös Loránd University
ISSN (Print)1215-5918

Keywords

  • feasibility problems
  • Anstreicher-Terlaky type monotonic simplex algorithms
  • linear programming
  • degeneracy

Fingerprint

Dive into the research topics of 'Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems'. Together they form a unique fingerprint.

Cite this