Optimization Online


Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

IllÚs Tibor (illes***at***math.elte.hu)
Bilen Filiz (filiz.bilen***at***emu.edu.tr)
Csizmadia Zsolt (csisza***at***cs.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 )



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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society