A primal deficient-basis simplex algorithm for linear programming

The proposed algorithm has been implemented and tested on a set of 50 Netlib test problems as well as a set of 15 much larger real-world problems, including 8 Kennington and 5 BPMPD problems. It significantly outperformed MINOS 5.3 in terms of both iteration counts and run time. In particular, these results reveal that there is no inevitable correlation between an algorithm's inefficiency and degeneracy (contradicting common belief).