Methods for solving large-scale bounded linear programs

The purpose of this thesis is to present two methods for solving large-scale linear programs which impose certain restrictions on the values of the variables. By taking advantage of the restrictions on the variables, the restrictiveness of working with a large basis, which would be required if the simplex procedure was applied directly, is avoided.

Two different types of structure for the restrictions on the variables will be considered. The first type is composed of restrictions which require each variable not to exceed a specified limit. In this case, these upper limits are not explicitly represented in solving the problem. Instead, from a feasible basis an "effective" basis is defined, where the nonbasic variables can equal their upper limit or zero. Conditions are then set to show when an optimal solution is found, to find candidates to enter the effective basis, and what value these candidates should attain. The second type is composed of restrictions that restrict the total value of certain linear sums of the variables. In this case, a "working" basis, much smaller than a normal feasible basis, is derived from a feasible basis. This "working" basis is used to find all the necessary information to optimize the problem.