A Dual Generalized Upper Bounding Technique

A Generalized Upper Bounding technique, similar to that introduced by Dantzig and Van Slyke [Dantzig, G. B., Van Slyke, R. M., 1967. Generalized upper bounding techniques. Journal of Computer and System Sciences. Vol. 1 pp. 213–226.], for solving large linear programs “with m + L equations (m ≪ L), L of which have the property that each variable has at most one nonzero coefficient in them” is offered. The algorithm is a variant of the dual simplex method, uses a working basis of order m and allows implementation of various pivoting strategies. The necessary modifications to the algorithm for handling bounded variables are also described.