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.

• 저널Management Science · 17(5) · 269–284
• 토픽Advanced Optimization Algorithms Research · Numerical Analysis
• DOI10.1287/mnsc.17.5.269
• 저자Michael D. Grigoriadis