Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation

During the last fifteen years the dual simplex method has become a strong contender in solving large scale LP problems. However, the lack of descriptions of important implementation details in the research literature has led to a great performance gap between open–source research codes and commercial LP–systems. In this paper we present the mathematical algorithms, computational techniques and implementation details, which are the key factors for our dual simplex code to close this gap. We describe how to exploit hyper–sparsity in the dual simplex algorithm.