  


AnstreicherTerlaky type monotonic simplex algorithms for linear feasibility problems
Illés Tibor (illesmath.elte.hu) Abstract: We define a variant of Anstreicher and Terlaky's (1994) monotonic buildup (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, AnstreicherTerlaky 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  