Re: [Help-glpk] pivot rules in lpx_simplex

[Andrew Makhorin]

>   If there are multiple choice of entering and leaving variables
>during choosing a pivot, what strategy has been applied in the 
>implementation of lpx_simplex? Is it smallest subscript rule or some 
>other rule to avoid cycling? Can anyone reply to this please?

By default lpx_simplex uses the steepest edge pricing (for both primal
and dual versions) proposed in:

   D. Goldfarb and J.K. Reid. A Practicable Steepest-Edge Simplex
   Algorithm. Math.Prog., Vol. 12, no. 3, pp. 361-371.

   J.J. Forrest and D. Goldfarb. Steepest-edge simplex algorithms
   for linear programming. Math.Prog., 57:341-374, 1992.

and the ratio test (also for both primal and dual versions) proposed
in:

   P.M.J. Harris. Pivot selection methods of the Devex LP code.
   Math.Prog., 5:1-28, 1973.

Additionally, if some simplex step does not improve the objective,
a tolerance used on the second pass in Harris' test is slightly
increased that prevents cycling in most practical cases. However,
sometimes this does not help due to a combinatorial nature of the
problem (a classical example is: Ax = 0, x >= 0). Besides, lpx_simplex
can fall into an infinite loop due to numerical difficulties.

Andrew Makhorin