NEW ALGORITHMS AND CUTTING PLANE CONSTRAINTS FOR THE SOLUTION OF DIOPHANTINE LINEAR PROGRAMS.
Management sciences research rept. (Doctoral thesis),
CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION
Pagination or Media Count:
This thesis presents two computational algorithms for solving the integer linear programming problem and a class of cutting plane constraints that may be employed as part of an algorithmic solution strategy. The first algorithm, called the bound escalation method, is close related to the all-integer algorithm of Ralph Gomory. The principal point of contrast lies in the concept of the bounding form, which the method is designed specifically to create and then exploit. The second algorithm, called the multiphase-dual method, a more specialized method designed to solve the 0-1 linear programming problem. This method, which is combinatorial in nature, patterns after the additive algorithm of Egon Balas, and employs an array of tests applied in conjunction with a surrogate constraint to eliminate large portions of the solution space from consideration. The cutting plane constraints, finally, are generated from a general equation in two parameters. Theorems are proved which specify values for these parameters that yield cuts having certain properties not found in the other cuts in the literature. Author