Investigating phase 1 of the dual simplex

The paper performs a theoretical and computational analysis of a new dual simplex algorithm GDPO that is based on a piecewise linear phase 1 objective function. It concludes that it is able to considerably outperform the traditional dual phase 1 methods. It offers enhanced numerically stability and more effectiveness in coping with degeneracy. Tests on 48 real life problems indicate that the theoretically possible improvements are very likely to materialize in practice thus making this algorithm a prime candidate for inclusion in any modern simplex solver.