NEW ALGORITHMS AND CUTTING PLANE CONSTRAINTS FOR THE SOLUTION OF DIOPHANTINE LINEAR PROGRAMS.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1965
- Accession Number
- AD0618690
Entities
People
- Fred Glover
Organizations
- Carnegie Institute of Technology