5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I think you mean $x_{i,j}\in\Bbb N$. $\endgroup$ – TheSimpliFire Feb 7 at 10:35
  • $\begingroup$ @TheSimpliFire The first constraint set forces $x_{i,j}$ to be binary. $\endgroup$ – Mostafa Feb 7 at 13:01
  • $\begingroup$ @Mostafa Of course, my mistake. $\endgroup$ – TheSimpliFire Feb 9 at 11:26
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much for answering my question. Could you perhaps explain why changing ≤ to = does not change the complexity? I could not find a source stating that knapsack with equality sign is NP-hard. $\endgroup$ – Pete S Feb 6 at 14:01
  • $\begingroup$ Yes, I edit the post. $\endgroup$ – Mostafa Feb 6 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.