Accession Number : AD0688889

Title :   A BOUND-AND-SCAN ALGORITHM FOR PURE INTEGER LINEAR PROGRAMMING WITH GENERAL VARIABLES.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Hillier,Frederick S.

Report Date : 20 MAY 1969

Pagination or Media Count : 130

Abstract : The report presents the theory underlying the bound-and-scan algorithm for solving the pure integer linear programming problem with general integer variables. This algorithm proceeds by obtaining tight bounds or conditional bounds on the relevant values of the respective variables, and then identifying a sequence of constantly improving feasible solutions by scanning the relevant solutions. New encouraging computational experience is reported which suggests that this algorithm should compare favorably in efficiency with existing algorithms. Plans for investigating ways of further increasing the efficiency of the algorithm and of extending it to more general problems (including the mixed-integer case) also are outlined. The report also gives a listing of a new FORTRAN code for the algorithm and 30 new test problems.

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), OPTIMIZATION, ITERATIONS, COMPUTER PROGRAMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE