Generalized assignment problem

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 tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

In the following, we have n kinds of items, ${\displaystyle a_{1}}$ through ${\displaystyle a_{n}}$ and m kinds of bins ${\displaystyle b_{1}}$ through ${\displaystyle b_{m}}$. Each bin ${\displaystyle b_{i}}$ is associated with a budget ${\displaystyle t_{i}}$. For a bin ${\displaystyle b_{i}}$, each item ${\displaystyle a_{j}}$ has a profit ${\displaystyle p_{ij}}$ and a weight ${\displaystyle w_{ij}}$. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin ${\displaystyle b_{i}}$ the total weight of assigned items is at most ${\displaystyle t_{i}}$. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.

Mathematically the generalized assignment problem can be formulated as an integer program:

${\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

The generalized assignment problem is NP-hard.^[1] However, there are linear-programming relaxations which give a ${\displaystyle (1-1/e)}$-approximation.^[2]

For the problem variant in which not every item must be assigned to a bin, there is a family of algorithms for solving the GAP by using a combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for the GAP.^[3]

Using any ${\displaystyle \alpha }$-approximation algorithm ALG for the knapsack problem, it is possible to construct a (${\displaystyle \alpha +1}$)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept. The algorithm constructs a schedule in iterations, where during iteration ${\displaystyle j}$ a tentative selection of items to bin ${\displaystyle b_{j}}$ is selected. The selection for bin ${\displaystyle b_{j}}$ might change as items might be reselected in a later iteration for other bins. The residual profit of an item ${\displaystyle x_{i}}$ for bin ${\displaystyle b_{j}}$ is ${\displaystyle p_{ij}}$ if ${\displaystyle x_{i}}$ is not selected for any other bin or ${\displaystyle p_{ij}}$ – ${\displaystyle p_{ik}}$ if ${\displaystyle x_{i}}$ is selected for bin ${\displaystyle b_{k}}$.

Formally: We use a vector ${\displaystyle T}$ to indicate the tentative schedule during the algorithm. Specifically, ${\displaystyle T[i]=j}$ means the item ${\displaystyle x_{i}}$ is scheduled on bin ${\displaystyle b_{j}}$ and ${\displaystyle T[i]=-1}$ means that item ${\displaystyle x_{i}}$ is not scheduled. The residual profit in iteration ${\displaystyle j}$ is denoted by ${\displaystyle P_{j}}$, where ${\displaystyle P_{j}[i]=p_{ij}}$ if item ${\displaystyle x_{i}}$ is not scheduled (i.e. ${\displaystyle T[i]=-1}$) and ${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$ if item ${\displaystyle x_{i}}$ is scheduled on bin ${\displaystyle b_{k}}$ (i.e. ${\displaystyle T[i]=k}$).

Formally:

Set ${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

For ${\displaystyle j=1,\ldots ,m}$ do:

Call ALG to find a solution to bin ${\displaystyle b_{j}}$ using the residual profit function ${\displaystyle P_{j}}$. Denote the selected items by ${\displaystyle S_{j}}$.

Update ${\displaystyle T}$ using ${\displaystyle S_{j}}$, i.e., ${\displaystyle T[i]=j}$ for all ${\displaystyle i\in S_{j}}$.

• Assignment problem