NP-hardness of a special case of multiple choice knapsack problem

Question

Let us consider the following problem:

\begin{align} \max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\ \text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\ &\quad \sum_{i=1}^n\sum_{j=1}^m w_i\cdot x_{i,j} = W & \\ &\quad x_{i,j} \in \mathbb{B} &\forall i =1,\dots,n,\quad \forall j =1,\dots,m \end{align}

I would like to prove that this problem is NP-hard. I know that the multiple choice knapsack problem is NP-hard. However, there are two substantial differences with our problem:

1. The weights of all item within a class are equal (i.e. we have $w_i$ instead of $w_{i,j}$).
2. The capacity constraint must be satisfied by equality.

Therefore, my problem is a special case of the multiple choice knapsack problem, or: multiple choice knapsack problem is a generalisation of my problem. Therefore, I suspect that I can not reduce my problem from the multiple choice knapsack problem.

Still, I strongly suspect that the problem above is NP-hard. Am I missing something?

Answer 1

I think the problem is NP-hard since:

1. it will reduce to the 0-1 Knapsack problem with an equality constraint; and,

2. changing $\leq$ to $=$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below).

So, your problem is NP-hard as 0-1 Knapsack is.

P.S. To see why (2) is correct, suppose all weights and values are equal. Then the problem reduces to the subset sum problem, that is also NP-hard.