The positive edge is a new pricing rule for the primal simplex: it identifies, with a probability error less than or equal to 2^-30 in single precision binary floating-point format and 2^-62 in double precision format, variables allowing for non-degenerate pivots. These are identified directly from a short calculation on the original coefficients of the constraint matrix. The complexity is the same as for the computation of the reduced cost. If such a variable has a negative reduced cost, it strictly improves the objective function value when entered into the basis.

The preliminary computational experiments made with CPLEX show its high potential. We designed a simple algorithm using two external procedures: one identifies variables that allow for non-degenerate pivots while the other identifies variables with negative reduced cost. These are sent to the primal simplex algorithm of CPLEX. It has been tested on fourteen medium-sized aircraft fleet assignment instances (5000 constraints and 25 000 variables), two large-scale manpower planning problems (100 000 constraints and 450 000 variables), and nine PDS instances from the Mittelmann library. All these problems are highly degenerate. On the first group, our algorithm is 7.4 times faster than CPLEX on average and the number of pivots is almost reduced by a factor 2. On the second and third groups, it is 50% faster and the number of pivots is decreased by 2.4 and 3.6, respectively. It has also been tested on Fome12 and Fome13 from the Mittelmann library. For these two highly dense problems, our simple implementation failed. The integration of the positive edge rule within a primal simplex code should prevent such cases by eliminating the external procedures and taking advantage of partial pricing strategies.