A Branch and Bound Algorithm for the Generalized Assignment Problem.

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)

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1973
Accession Number
AD0774033

Entities

People

  • G. Terry Ross
  • Richard M. Soland

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Core Storage
  • Data Storage Systems
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Magnetic Cores
  • Mathematics
  • Memory Devices
  • Simplex Method

Readers

  • Operations Research