
Accession Number : AD0618690
Title : NEW ALGORITHMS AND CUTTING PLANE CONSTRAINTS FOR THE SOLUTION OF DIOPHANTINE LINEAR PROGRAMS.
Descriptive Note : Management sciences research rept. (Doctoral thesis),
Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION
Personal Author(s) : Glover,Fred
Report Date : FEB 1965
Pagination or Media Count : 181
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 allinteger 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 'multiphasedual method,' a more specialized method designed to solve the 01 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)
Descriptors : (*LINEAR PROGRAMMING, ALGEBRA), (*NUMERICAL ANALYSIS, LINEAR PROGRAMMING), COMBINATORIAL ANALYSIS, SEARCH THEORY, OPERATIONS RESEARCH
Distribution Statement : APPROVED FOR PUBLIC RELEASE