A new version of the Improved Primal Simplex for degenerate linear programs

作者：Raymond Vincent^*; Soumis Francois; Orban Dominique

来源：Computers & Operations Research, 2010, 37(1): 91-98.

DOI：10.1016/j.cor.2009.03.020

• Linear programming
• Primal simplex
• Degeneracy

The Improved Primal Simplex (IPS) algorithm [Elhallaoui I, Metrane A, Desaulniers; G, Soumis F. An Improved Primal Simplex algorithm for degenerate linear programs. SIAM journal of Optimization, submitted for publication] is a dynamic constraint reduction method particularly effective on degenerate linear programs. It is able to achieve a reduction in CPU time of over a factor of three on some problems compared to the commercial implementation of the simplex method CPLEX. We present a number of further improvements and effective parameter choices for IPS. On certain types of degenerate problems, our improvements yield CPU times lower than those of CPLEX by a factor of 12.

• 出版日期2010-1