An Improved Primal Simplex Algorithm for Degenerate Linear Programs
Authors:
- 1 November 2011
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 23 (4) , 569-577
Abstract
Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithms for solving linear programs. It is often very efficient when there is very little degeneracy, but it often struggles in the presence of high degeneracy, executing many pivots without improving the objective function value. In this paper, we propose an improved primal simplex algorithm that deals with this issue. This algorithm is based on new theoretical results that shed light on how to reduce the negative impact of degeneracy. In particular, we show that, from a nonoptimal basic solution with p positive-valued variables, there exists a sequence of at most m - p + 1 simplex pivots that guarantee the improvement of the objective value, where m is the number of constraints in the linear program. These pivots can be identified by solving an auxiliary linear program. Finally, we briefly summarize computational results that show the effectiveness of the proposed algorithm on degenerate linear programs.Keywords
This publication has 12 references indexed in Scilit:
- A new version of the Improved Primal Simplex for degenerate linear programsComputers & Operations Research, 2010
- Multi-phase dynamic constraint aggregation for set partitioning type problemsMathematical Programming, 2008
- Bi-dynamic constraint aggregation and subproblem reductionComputers & Operations Research, 2008
- Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithmsComputational Optimization and Applications, 2007
- Dynamic Aggregation of Set-Partitioning Constraints in Column GenerationOperations Research, 2005
- A basis-deficiency-allowing variation of the simplex method for linear programmingComputers & Mathematics with Applications, 1998
- On the solution of highly degenerate linear programmesMathematical Programming, 1988
- New Finite Pivoting Rules for the Simplex MethodMathematics of Operations Research, 1977
- Linear Programming and Extensions1963
- Optimality and Degeneracy in Linear ProgrammingEconometrica, 1952