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