Search

In the paper the author re-examines some of the available methods for pricing out the columns in the simplex method and point out their potential advantages and disadvantages. In particular it is shown that a simple formula for updating the pricing vector can be used with some advantage in the standard product form simplex algorithm and with very considerable advantage in two recent developments: P.M.J. Harris's dynamic scaling method and the Forrest-Tomlin method for maintaining triangular factors of the basis. (Author).

In recent years computational methods for solving large scale mathematical programming problems have improved enormously. The most fundamental of these improvements have been linear programming, where problems are becoming both larger and more complex in their own right and as sub-problems in non-linear and integer programs. Sophisticated new techniques have enhanced the inversion, pivot selection and updating steps of the simplex algorithm, while generalized upper bounding (GUB) has made possible the solution of some problems of staggering size. In integer and non-convex programming new techniques such as special order sets and pseudo-costs have advanced the art to a stage where problems with a few thousand constraints can be handled with confidence. Similarly improvements in the Method of Approximation Programming (MAP) have made the solution of large and complex non-linear programs computationally attractive. (Author).

This note reports the results of some experiments on measuring the accuracy of a group of methods for updating the inverse in the simplex method. These methods are the standard product form, the Bartels-Golub method and the Forrest-Tomlin update. Then experiments, carried out on small to medium size models, were somewhat disturbing in that no method showed consistent superiority, and in that the error measurements that were used showed very erratic behavior.

This paper presents a method for finding the minimum (l sub infinity)-norm solution to a set of consistent linear equations using a form of parametric linear programming. In this application the upper and lower bounds of all the variables are parametrized, and the author works with only the original variables and constraints. Computational results indicate that the method is superior to both a primitive linear programming approach to the problem and to other, more specialized methods, which have been suggested.

In this note the authors describe a reasonably efficient implementation of Scolnik's linear programming approach. The authors became interested in using the code to test the usefulness of this approach as a starting heuristic or 'crashing' technique, as the method is known to fail in general. The computational experience, however, leads the authors to believe that the method is too costly even for this modest objective.

This note describes a new accuracy test for the Forrest-Tomlin method for updating triangular factors of the basis, based on standard error analysis techniques. This test has proved very useful in practice when the method is applied to digitally unstable models.