Strategies for Creating Advanced Bases for Large-Scale Linear Programming Problems

The performance of the revised sparse simplex method, or its variants, for the solution of large scale linear programming problems can be considerably enhanced if an advanced starting basis is introduced instead of the traditional all-logical initial basis. We consider three such procedures known as crash procedures to obtain advanced starting points for the revised sparse simplex: 1) We extend traditional crash procedures whereby triangularity of the basis is always maintained and take advantage of the problem characteristics; we apply additional criteria for determining the entering structural variables and their position in the basis. 2) We allow the triangularity to be slightly “violated,” and make some cheap pivot steps to find a better basis. 3) We use the iterative successive-over-relaxation technique to compute a non-extreme point solution and make a crossover to a basic solution. In this article, we first review the work done by other researchers. Then we present an analysis of issues, followed by a description of the techniques and our computational experience.