Accession Number : AD0659996

Title :   TWO ALGORITHMS FOR SOLVING THE INDEPENDENT MULTI-DIMENSIONAL KNAPSACK PROBLEM.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Green,Christopher J.

Report Date : MAY 1967

Pagination or Media Count : 33

Abstract : Two algorithms are presented for solving the multi-dimensional bounded knapsack problem. Algorithm I is an adaptation of the Gilmore-Gomory algorithm for the one dimensional problem. Algorithm II, less compact but probably more efficient, is based upon the structure of the problem. The procedures developed examine the tree of possible solutions, form bounds, and successively narrow-down the tree that will be enumerated to prove optimality of the solution. This algorithm uses linear programming, dominance considerations, marginal-analysis of value, and some heuristics to obtain a very small set of combinations that have to be tried to assure optimality - thus making the algorithm computationally practical on present computers. (Author)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), (*COMMERCE, MANAGEMENT PLANNING AND CONTROL), (*COMBINATORIAL ANALYSIS, OPTIMIZATION), RAILROADS, FLOW CHARTING, NUMERICAL METHODS AND PROCEDURES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE