Methods for solution to the integer linear programming problem
The purpose of this thesis is to consider methods for the solution to the integer constrained linear programming problem (ILP). To be considered are the method of reducing the feasible solution set by introduction of cutting plane constraints, and the method of reducing the ILP to a knapsack formulation.
Chapter I introduces the ILP and the theoretical basis for the cutting plane approach, along with a method for choosing the cutting plane. The all-integer algorithm with its special choice of cutting planes is then presented in Chapter II.
The knapsack problem, a special case of the ILP, is discussed in Chapter III. Following in Chapter IV is a proof that any ILP in bounded variables can be reduced to a knapsack problem in bounded variables. Finally, an algorithm is presented for solution of the knapsack problem in bounded variables.
Thesis76.H288.pdf
2.06 MB
Adobe PDF
8db15f3a801b3c95a6dc886b0aa81bad