Groupe d’études et de recherche en analyse des décisions

Positive Edge: A Pricing Criterion for the Identification of Non-Degenerate Simplex Pivots

Mehdi Towhidi Polytechnique Montréal, Canada

The positive edge is a new pricing rule for the primal simplex method: it identifies, with a probability of 1 - 2^{−62}, variables allowing for non-degenerate pivots. Its computational complexity is the same as that of computing reduced costs. In this talk, we describe the positive edge rule and its integration within COIN-OR's CLP. We test our implementation on some highly degenerate LPs as well as more generic instances of Mittelmann's Benchmark.