Anti-Cycling Pivot Rules in Linear Optimization

Pivot algorithms for solving linear optimization problems traverse the set of basic solutions or bases of the inequality system describing the model, searching for a feasible solution, or an optimal feasible solution if the model also contains a cost function to be minimized or maximized. Feasibility preserving pivot algorithms for solving linear optimization problems, often called simplex-type methods, preserve primal feasibility while trying to achieve dual feasibility or vice versa. Monotonic Build Up algorithm of Anstreicher and Terlaky is a simplex-type algorithm with interesting properties. We develop a pivot algorithm with similar properties for solving the feasibility problem of linear optimization in particular. To guarantee finiteness of our Monotonic Build Up simplex algorithm we incorporate s-monotone index selection rules into the general framework of the algorithm which are to be utilized whenever there is competition among the basic variables to leave the basis and among the nonbasic variables to enter the basis. We also use a specialized recursive procedure for handling strongly degenerate bases. We prove finiteness of the algorithm and analyze its computational complexity under some assumptions. As opposed to simplex-type methods criss-cross pivot algorithm preserves neither primal nor dual feasibility. We use criss-cross algorithm together with s-monotone index selection rules to solve feasibility problem of oriented matroids and and also prove its finiteness.