Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

Illés Tibor (illesmath.elte.hu)
Bilen Filiz (filiz.bilenemu.edu.tr)
Csizmadia Zsolt (csiszacs.elte.hu)

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\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number of constraints. The constant $\Delta$ 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 $2m$. 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 problem, Anstreicher-Terlaky type monotonic simplex algorithms, degeneracy, linear programming

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation:

Download:

Entry Submitted: 09/05/2005
Entry Accepted: 09/05/2005
Entry Last Modified: 05/29/2007

Modify/Update this entry