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.
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

Fingerprint

Linear programming
Polynomials
Upper bound

Keywords

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

Cite this

Filez, B., Zsolt, C., & Illes, T. (2005). Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems. (Operations Research Report). Budapest.
Filez, Blien ; Zsolt, Csizmadia ; Illes, Tibor. / Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems. Budapest, 2005. 25 p. (Operations Research Report).
@book{0b0813e40f464292a9a065ec8e3f9f5d,
title = "Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems",
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.",
keywords = "feasibility problems, Anstreicher-Terlaky type monotonic simplex algorithms, linear programming, degeneracy",
author = "Blien Filez and Csizmadia Zsolt and Tibor Illes",
year = "2005",
month = "5",
language = "English",
volume = "2005",
series = "Operations Research Report",
publisher = "E{\"o}tv{\"o}s Lor{\'a}nd University",

}

Filez, B, Zsolt, C & Illes, T 2005, Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems. Operations Research Report, vol. 2005, Budapest.

Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems. / Filez, Blien; Zsolt, Csizmadia; Illes, Tibor.

Budapest, 2005. 25 p. (Operations Research Report).

Research output: Book/ReportScholarly edition

TY - BOOK

T1 - Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems

AU - Filez, Blien

AU - Zsolt, Csizmadia

AU - Illes, Tibor

PY - 2005/5

Y1 - 2005/5

N2 - 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.

AB - 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.

KW - feasibility problems

KW - Anstreicher-Terlaky type monotonic simplex algorithms

KW - linear programming

KW - degeneracy

UR - http://www.cs.elte.hu/opres/orr/download/ORR05_3.pdf

M3 - Scholarly edition

VL - 2005

T3 - Operations Research Report

BT - Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems

CY - Budapest

ER -

Filez B, Zsolt C, Illes T. Anstreicher-Terlaky Type Monotonic Simplex Algorithms for Linear Feasibility Problems. Budapest, 2005. 25 p. (Operations Research Report).