[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] pivot rules in lpx_simplex

From: Andrew Makhorin
Subject: Re: [Help-glpk] pivot rules in lpx_simplex
Date: Mon, 12 Jul 2004 17:34:06 +0400

>   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

   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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]