[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
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