Abstract
In certain linear programs, especially those derived from integer programs, large numbers of constraints may have very simple form. Examples are:x ij ≤ 1 (simple upper bounds [SUB]),Σ i x ij = 1 (generalized upper bounds [GUB]) andx ij ≤ y i (variable upper bounds [VUB]). A class of constraints called generalized VUB [GVUB] is introduced which includes GUB and VUB as special cases. Also introduced is a method for representing GVUB constraints implicitly within the mechanics of the simplex method.
Similar content being viewed by others
References
R. Dutton, G. Hinman and C.B. Millham, “The optimal location of nuclear-power facilities in the pacific northwest”,Operations Research 22 (3) (1974) 478–487.
G. Roodman and L. Schwarz, “The dynamic plant location problem”, working paper, University of Rochester (1974).
L.E. Schrage, “Implicit representation of variable upper bounds in linear programs”,Mathematical Programming Study 4 (1975) 118–132.
Author information
Authors and Affiliations
Additional information
Research supported in part by the Mobil Oil Corporation.
Rights and permissions
About this article
Cite this article
Schrage, L. Implicit representation of generalized variable upper bounds in linear programming. Mathematical Programming 14, 11–20 (1978). https://doi.org/10.1007/BF01588948
Issue Date:
DOI: https://doi.org/10.1007/BF01588948