Multiple Knapsack Problems
Why
We consider knapsack problems in which there is more than one knapsack.
Definition
Given $p: \set{1, \dots , n} \to \R $, $w:
\set{1, \dots , n} \to \R $ and $c \in
\R _+^n$, find $x: \set{0,\dots ,m} \times
\set{0, \dots , n} \to \{0,1\}$ to
\[
\begin{aligned}
\text{maximize} & \quad \textstyle \sum_{i = 1}^m \sum_{j =
1}^{n} p_j x_{ij} \\
\text{subject to} & \quad \textstyle \sum_{j = 1}^n w_jx_{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}
\]