Content deleted Content added
Corrected formulation. Items are required to be assigned to exactly one bin, see for example Ross, G. Terry, and Richard M. Soland. "A branch and bound algorithm for the generalized assignment problem." Mathematical programming 8.1 (1975): 91-103. |
|||
Line 8:
In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the [[assignment problem]]. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the [[Knapsack problem]].
==explation of defination==
In the following, we have ''n'' kinds of items, <math>a_1</math> through <math>a_n</math> and ''m'' kinds of bins <math>b_1</math> through <math>b_m</math>. Each bin <math>b_i</math> is associated with a budget <math>t_i</math>. For a bin <math>b_i</math>, each item <math>a_j</math> has a profit <math>p_{ij}</math> and a weight <math>w_{ij}</math>. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin <math>b_i</math> the total weight of assigned items is at most <math>t_i</math>. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.
| |||