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 -