Experiments with the Reduced Gradient Method for Linear Programming

This article deals with some methods for linear programming which generate a monotonically improving sequence of feasible solutions. Examples of such methods are the simplex method and the reduced gradient method. A larger class of such methods as well as their convergence has been discussed in a recent article by Kallio and Porteus. We have implemented a version of such methods in the SESAME system developed by Orchard-Hays. This version resembles the reduced gradient method except that only a subset of nonbasic variables to be changed is considered at each iteration. We shall try out several modifications of this basic version. These modifications are concerned with the choice of an initial basis and an initial solution, with strategies for finding a feasible solution, as well as with strategies for determining the direction of change for a feasible solution at each iteration. We have experimented with moderate sized nonstructured as well as dynamic problems. Compared with the simplex method, the overall performance of such methods is about equal in the case of linear programs with no particular structure. For dynamic LP we have obtained some encouraging results. Although we have been able to experiment with only a few problems, so far it seems that using specially defined starting basis and initial nonbasic solution allow a reduction by a factor of eight in the computing time of the reduced gradient method. This starting basis is chosen so that its columns are likely to appear also in an optimal basis. For the initial solution, available information, such as current level of activities in real life, may be employed. Of course, our starting basis for dynamic LP may be used also in the simplex method, and, indeed this results in a considerable improvement of efficiency