Multiple Working Bases for Generalized and Variable Upper Bounding Linear Programs

Special structures are usually noticed when a linear program represents a large scale system of inequalities associated with a management application. Such models are formulated frequently when describing production or capital budgeting problems. These linear programs of specific structures may contain both generalized upper bounding (GUB) and/or variable upper bounding (VUB) constraints. A variant of the revised simplex method is provided in this chapter for these types of linear programs so that the basis size is reduced. Based on some theoretical results derived, a special algorithm using two working bases is provided for pivoting, pricing, and inverting. Its implementation is shown to be computationally efficient.