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 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)

Descriptors :   (*LINEAR PROGRAMMING, ALGEBRA), (*NUMERICAL ANALYSIS, LINEAR PROGRAMMING), COMBINATORIAL ANALYSIS, SEARCH THEORY, OPERATIONS RESEARCH

Distribution Statement : APPROVED FOR PUBLIC RELEASE