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 -