Generalized Assignment Problems
Why
We consider a multiple knapsack problem in which different knapscaks have different profits and weights.
Definition
Denote by $[m]$ and $[n]$ the sets $\{1,
\dots , m\}$ and $\{1, \dots , n\}$, respectively.
Given $p: [m] \times [n] \to \R $, $w: [m]
\times [n] \to \R _+$, $c: [m] \to \R _+$,
find $x: [m] \times [n] \to \{0,1\}^n$ to
\[
\begin{aligned}
\text{maximize} & \quad \textstyle \sum_{i = 1}^m \sum_{j =
1}^{n} p_{ij} x_{ij} \\
\text{subject to} & \quad \textstyle \sum_{j = 1}^n
w_{ij}x_{ij} \leq c_i , \quad i = 1, \dots , n\\
& \quad \textstyle \sum_{j = 1}^{n} x_{ij} \leq 1, \quad i
= 1, \dots , n \\
& \quad x_{ij} \in \{0,1\} \quad i = 1, \dots , m, j = 1,
\dots , n
\end{aligned}
\]