An implementation of the simplex method for linear programming problems with variable upper bounds

Special methods for dealing with constraints of the formx _j x _k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constraints and show how it can be implemented using triangular basis factorizations.This research was partially supported by National Science Foundation Grant ECS-7921279 and by a Guggenheim fellowship.