Accession Number : AD0774033

Title :   A Branch and Bound Algorithm for the Generalized Assignment Problem.

Descriptive Note : Research rept.,

Corporate Author : TEXAS UNIV AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s) : Ross,G. Terry ; Soland,Richard M.

Report Date : SEP 1973

Pagination or Media Count : 23

Abstract : The paper describes what is termed the generalized assignment problem. It is a generalization of the ordinary assignment problem of linear programming in which multiple assignments of tasks to agents are limited by some resource available to the agents. A branch and bound algorithm is developed that solves the generalized assignment problem by solving a series of 0 - 1 knapsack problems to determine the bounds. To minimize magnetic core storage requirements, a branch search technique is used to generate and examine the branch and bound tree. Computational results are cited for problems with up to 4,000 (0 - 1) variables. (Author)

Descriptors :   *Linear programming, Algorithms, Computations

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE