<p>In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539799356265" rel="noreferrer">http://epubs.siam.org/doi/abs/10.1137/S0097539799356265</a>) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not fixed. You can find hardness results as function of d in that paper.</p>

CC BY-SA 3.0
2015-05-20T01:10:54.907Z
2015-05-20T01:10:54.907Z
Chandra Chekuri
<p>The Knapsack Problems text by Kellerer et al. cites the two references below as proving that multidimensional knapsack is strongly NP-hard already in the special case of CARDINALITY 2-KP (two-dimensional, with unit values). It also reproduces a proof, reducing from EQUIPARTITION, i.e., the existence of an FPTAS for CARDINALITY 2-KP implies that the EQUIPARTITION decision problem can be solved in polynomial time.</p>

<p>I believe the augmented resources version of the (fixed dimension) problem, where you're permitted to exceed the bounds by $\epsilon$ does admit an FPTAS, however.</p>

<p>G.Y. Gens and E.V. Levner. Computational complexity of approximation algorithms for combinatorial problems. In Mathematical Foundations o f Computer Science, volume 74 of Lecture Notes in Computer Science, pages 292-300. Springer, 1979.</p>

<p>B. Korte and R. Schrader. On the existence of fast approximation schemes. In O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, editors, Nonlinear Programming, volume 4, pages 415-437. Academic Press, 1981.</p>

CC BY-SA 3.0
2015-05-18T06:36:59.107Z
2015-05-18T06:36:59.107Z
Matt
<p>A possible reduction is from Exact Cover by Three Sets (X3C) (which is strongly NP-hard):</p>

<p><b>Instance</b>: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F_i = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}, i=1,...,m$ of 3-elements subsets of $X$ (triples);<br>
<b>Question</b>: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.</p>

<p>Reduction: given an instance of X3C, just pick a knapsack with $3n$ dimensions each one with maximum capacity $c_i = 1$; pick $n$ objects corresponding to the subsets $F_i$ with profit $1$ and assign weight $a_{ij} = 1$ if and only if $x_j$ is contained in set $F_i$. You can reach a total profit of $n$ if and only if the original X3C problem has a solution, i.e. you can fill the whole knapsack; the objects in the knapsack correspond to the subsets $F_i$ that form a valid exact cover of $X$.</p>

CC BY-SA 3.0
2014-04-01T15:35:29.197Z
Darn, I should have looked there first... Thanks, that closes the question. (Still shocked that none of the OR publications I read got that one right.)
Sebastian
CC BY-SA 3.0
2014-04-01T15:47:58.050Z
Nope, looking more closely, this is not "it": Martello and Toth deal with the multi KP problem (you can sort the items into multiple knapsacks). But I am interested in the **multidimensional** KP: each item goes into all knapsacks simultaneously. For example, volume and mass of all items must both be below some given thresholds, but obviously, they are not connected.
Sebastian
CC BY-SA 3.0
2014-04-02T08:13:28.453Z
You're right, they deal with the multi KP. The reduction from X3C to *multidimensional KP* in the modified answer should work.
Marzio De Biasi
CC BY-SA 3.0
2014-04-01T15:04:37.080Z
2014-04-02T08:09:44.560Z
2014-04-02T08:09:44.560Z
Marzio De Biasi
<p>I believe you could also reduce from bin-packing which is strongly NP-complete according to wikipedia.</p>

<p>Consider this instance of MD-KS:
$$
\max \sum_{i = 1, j = 1}^{n, m} x_{i,j} \\
s.t.: \sum_{j} x_{i,j} \le 1 \\
\;\;\;\;\;\;\;\; \sum_{i} a_{i} x_{i,j} \le b \\
\;\;\;\;\;\;\;x_{i, j} \in \{0, 1 \}
$$</p>

<p>The optimization problem above finds the maximum number of objects out of $n$ objects, which can be fit into $m$ bins of size $b$ (size/weight of object $i$) is $a_i$.</p>

<p>Bin Packing (decision problem): Given $n$ objects, can we fit them in $m$ bins?
Solution: Run optimization above and return true if the optimal value is $n$. False otherwise.</p>

<p>The size of MD-KP here is $mn$ variables and $n + m$ constraints. The size of corresponding bin-packing problem is $n$ objects and $m$ bins. In any case, the sizes are polynomial-ly related so I believe the reduction is valid.</p>

CC BY-SA 3.0
2014-04-01T22:08:11.267Z
Presumably, @Sebastian is trying to show that the problem is strongly NP-hard with a constant number of constraints.
Austin Buchanan
CC BY-SA 3.0
2014-04-01T23:21:09.493Z
For fixed $m$, isn't the original problem polynomial in the length of input? Also, the original problem needs $O(nm)$ coefficients and so does the instance above.
Ehsan
CC BY-SA 3.0
2014-04-02T02:25:19.413Z
If you only wanted to show that the problem is strongly NP-hard for an arbitrary number of ''dimensions'', then yes your reduction works. I think it is more interesting to ask--does it remain strongly NP-hard in 2 or 3 ''dimensions''?
Austin Buchanan
CC BY-SA 3.0
2014-04-02T19:53:26.657Z
There are three lines in this wikipedia article that I find relevant to this discussion. The third line says and I quote "For any fixed m \ge 2, these problems do admit a pseudo-polynomial time algorithm (similar to the one for basic knapsack) and a PTAS.[2]". If this is true, then we the MD-KS is not strongly NP if "m" is a fixed number.
Section (Multiple Constraints) of this: http://en.wikipedia.org/wiki/List_of_knapsack_problems
Ehsan
CC BY-SA 3.0
2014-04-01T21:39:14.973Z
2014-04-01T21:39:14.973Z
Ehsan
<p>Ok, let me try to answer this myself:</p>

<ul>
<li>I was looking for a <em>reference</em>, not a proof. My hope was that it is in fact a two-line proof, and that I was just missing that. This seems to be true. The people who saw it, never wrote it up; everybody else just repeated the fact, without seeing the proof, I guess.</li>
<li>You can use reduction from <em>any</em> problem that can be formulated as an ILP with
<ul>
<li>polynomial number of constraints/variables,</li>
<li>only non-negative (integer) coefficients in the ILP formulation and objective function,</li>
<li>bounded maximum coefficient in the ILP is (either constant or some polynomial in the size of the instance), and</li>
<li>all constraints are $\le$.</li>
</ul></li>
<li>Any problem that is NP-hard and <em>does not involve numbers</em>, is strongly NP-hard.</li>
<li>Just as (yet another) example, you can use the ILP formulation of <em>maximum independent set</em> as a multidimensional KP, where all coefficients are 0/1. This is the simplest ILP of any problem that I can think of.</li>
<li>This indeed results in a polynomial number of constraints (polynomial dimension), but:</li>
<li>For <em>fixed dimension</em>, there exists a polynomial <em>DP</em> algorithm for finding the best solution; so, it cannot be strongly NP-hard for fixed dimension (@Austin).</li>
</ul>

<p>Is all of that correct? Then, sorry for the mess. Otherwise, please tell me if/where I am wrong...</p>

CC BY-SA 3.0
2014-04-02T14:32:06.337Z
A reduction from vertex cover does not work, at least given your statement of multi-dimensional knapsack. The constraints should be of the $\le$ type. Max clique or set packing would work.
Austin Buchanan
CC BY-SA 3.0
2014-04-02T17:01:41.973Z
My fault, thanks. I have replaced vertex cover by maximum independent set, the other side of the coin.
Sebastian
CC BY-SA 3.0
2015-05-19T01:08:00.517Z
Multidimensional knapsack is essentially the same as what are called packing integer programs (PIPs) which captures max independent set as a special case, as you observe.
Chandra Chekuri
CC BY-SA 3.0
2014-04-02T06:00:03.423Z
2014-04-02T17:05:40.050Z
2014-04-02T17:05:40.050Z
Sebastian
<p>Who can point me to a reference where it is actually <strong>shown</strong> that multidimensional knapsack is <strong>strongly NP-complete</strong>? I have found loads of papers where they claim it is, without citation; I have found another load where they cite Garey &amp; Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey &amp; Johnson as "An introduction to" instead of "A guide to", so these authors probably copied from one another. In fact, some authors claim that it is <strong>not</strong> strongly NP-complete, an example is "The multidimensional 0–1 knapsack problem: An overview" by Freville, but the argument (generalize the DP for single-dimension knapsack) is obviously bogus, see below.</p>

<p><em>Multidimensional knapsack</em> tries to maximize $\sum_j c_j x_j$ such that $\sum_j a_{ij} x_j \le b_j$ for $i=1,...,m$, with $x_i$ being integer $\ge 0$ (and all $c_j, a_{ij}, b_j$ being $\ge 0$). We can also demand $x_i \in \{0,1\}$, the 0/1-version of the problem. I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily).</p>

<p>Strongly NP-hard applies only to number problems, and restricts the (some) maximum of the numbers to be polynomial in the size of the problem instance (bits needed to encode it). Strongly NP-hard rules out the existence of a pseudopolynomial algorithm for the problem, with running time polynomial in the numbers that appear in the instance. The usual knapsack (single-dimensional) obviously has a pseudopolynomial algorithm (DP), but this algorithm cannot be generalized to multidimensional KP, as the dimension of the KP appears in the exponent of the running time. I hope that I did not mess up anything in my definitions...</p>

CC BY-SA 3.0
2014-04-02T07:49:55.350Z
The problem is NP-complete in the strong sens if the number of dimensions is a part of the input. If the number of dimensions is fixed then the problem is not strongly NP-complete.
Lamine
CC BY-SA 3.0
2014-04-02T09:46:43.677Z
Most problems become simpler if you fix any of their parameters. In other words, this observation is true but not helpful. Also see the discussion below.
Sebastian
CC BY-SA 3.0
2014-04-02T14:42:07.380Z
@Lamine citation?
Austin Buchanan
CC BY-SA 3.0
2014-04-02T15:17:00.057Z
@Sebastian: I agree with your answer below, a simple extension of the knapsack DP works for a fixed dimension $d$, with a running time of $O(W^d)$. The next question is whether it is $\sf{W[1]}$-hard when parameterized by $d$, it seems likely and would imply strong NP-completeness for unbounded $d$ isn't it?
NisaiVloot
CC BY-SA 3.0
2014-04-02T15:46:51.380Z
@AustinBuchanan First chapter of Pisinger's thesis. If the number of dimensions is fixed, the problem cannot be $\mathsf{NP}$-complete since it admits a pseudo-polynomial algorithm.
Lamine
CC BY-SA 3.0
2014-04-02T15:55:23.227Z
I believe that another reference is the book "Knapsack problems" by Kellerer, Pferschy & Pisinger. The preface contains an interesting comment: "The authors strongly believe in the necessity to do research not with an island mentality but in an open exchange of knowledge, opinions and ideas within an international research community." I wouldn't agree with Pissinger's use of the word "necessity" though.
NisaiVloot
<reference-request><np-hardness>
Multidimensional knapsack STRONGLY NP-complete
Sebastian
# Multidimensional knapsack STRONGLY NP-complete

(Asked by: username_0 on 2014-04-01)

Who can point me to a reference where it is actually **shown** that multidimensional knapsack is **strongly NP-complete**? I have found loads of papers where they claim it is, without citation; I have found another load where they cite Garey & Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey & Johnson as "An introduction to" instead of "A guide to", so these authors probably copied from one another. In fact, some authors claim that it is **not** strongly NP-complete, an example is "The multidimensional 0–1 knapsack problem: An overview" by Freville, but the argument (generalize the DP for single-dimension knapsack) is obviously bogus, see below.

*Multidimensional knapsack* tries to maximize $\sum\_j c\_j x\_j$ such that $\sum\_j a\_{ij} x\_j \le b\_j$ for $i=1,...,m$, with $x\_i$ being integer $\ge 0$ (and all $c\_j, a\_{ij}, b\_j$ being $\ge 0$). We can also demand $x\_i \in \{0,1\}$, the 0/1-version of the problem. I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily).

Strongly NP-hard applies only to number problems, and restricts the (some) maximum of the numbers to be polynomial in the size of the problem instance (bits needed to encode it). Strongly NP-hard rules out the existence of a pseudopolynomial algorithm for the problem, with running time polynomial in the numbers that appear in the instance. The usual knapsack (single-dimensional) obviously has a pseudopolynomial algorithm (DP), but this algorithm cannot be generalized to multidimensional KP, as the dimension of the KP appears in the exponent of the running time. I hope that I did not mess up anything in my definitions...

**Tags:** reference-request, np-hardness

> **Comments:**
> **username_1**: The problem is NP-complete in the strong sens if the number of dimensions is a part of the input. If the number of dimensions is fixed then the problem is not strongly NP-complete.  
> **username_0**: Most problems become simpler if you fix any of their parameters. In other words, this observation is true but not helpful. Also see the discussion below.  
> **username_2**: @username_1 citation?  
> **username_3**: @username_0: I agree with your answer below, a simple extension of the knapsack DP works for a fixed dimension $d$, with a running time of $O(W^d)$. The next question is whether it is $\sf{W[1]}$-hard when parameterized by $d$, it seems likely and would imply strong NP-completeness for unbounded $d$ isn't it?  
> **username_1**: @AustinBuchanan First chapter of Pisinger's thesis. If the number of dimensions is fixed, the problem cannot be $\mathsf{NP}$-complete since it admits a pseudo-polynomial algorithm.  
> **username_3**: I believe that another reference is the book "Knapsack problems" by Kellerer, Pferschy & Pisinger. The preface contains an interesting comment: "The authors strongly believe in the necessity to do research not with an island mentality but in an open exchange of knowledge, opinions and ideas within an international research community." I wouldn't agree with Pissinger's use of the word "necessity" though.  

---

## 5 answers

### Answer by username_4 on 2015-05-20. Score: 6

In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (<http://epubs.siam.org/doi/abs/10.1137/S0097539799356265>) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not fixed. You can find hardness results as function of d in that paper.


---

### Answer by username_5 on 2015-05-18. Score: 4

The Knapsack Problems text by Kellerer et al. cites the two references below as proving that multidimensional knapsack is strongly NP-hard already in the special case of CARDINALITY 2-KP (two-dimensional, with unit values). It also reproduces a proof, reducing from EQUIPARTITION, i.e., the existence of an FPTAS for CARDINALITY 2-KP implies that the EQUIPARTITION decision problem can be solved in polynomial time.

I believe the augmented resources version of the (fixed dimension) problem, where you're permitted to exceed the bounds by $\epsilon$ does admit an FPTAS, however.

G.Y. Gens and E.V. Levner. Computational complexity of approximation algorithms for combinatorial problems. In Mathematical Foundations o f Computer Science, volume 74 of Lecture Notes in Computer Science, pages 292-300. Springer, 1979.

B. Korte and R. Schrader. On the existence of fast approximation schemes. In O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, editors, Nonlinear Programming, volume 4, pages 415-437. Academic Press, 1981.


---

### Answer by username_6 on 2014-04-01. Score: 3

A possible reduction is from Exact Cover by Three Sets (X3C) (which is strongly NP-hard):

**Instance**: a set $X = \{ x\_1,x\_2,...,x\_{3n}\}$ and a family $F\_i = \{ ( x\_{i\_1}, x\_{i\_2}, x\_{i\_3}) \}, i=1,...,m$ of 3-elements subsets of $X$ (triples);  
**Question**: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

Reduction: given an instance of X3C, just pick a knapsack with $3n$ dimensions each one with maximum capacity $c\_i = 1$; pick $n$ objects corresponding to the subsets $F\_i$ with profit $1$ and assign weight $a\_{ij} = 1$ if and only if $x\_j$ is contained in set $F\_i$. You can reach a total profit of $n$ if and only if the original X3C problem has a solution, i.e. you can fill the whole knapsack; the objects in the knapsack correspond to the subsets $F\_i$ that form a valid exact cover of $X$.

> **Comments:**
> **username_0**: Darn, I should have looked there first... Thanks, that closes the question. (Still shocked that none of the OR publications I read got that one right.)  
> **username_0**: Nope, looking more closely, this is not "it": Martello and Toth deal with the multi KP problem (you can sort the items into multiple knapsacks). But I am interested in the **multidimensional** KP: each item goes into all knapsacks simultaneously. For example, volume and mass of all items must both be below some given thresholds, but obviously, they are not connected.  
> **username_6**: You're right, they deal with the multi KP. The reduction from X3C to *multidimensional KP* in the modified answer should work.  

---

### Answer by username_7 on 2014-04-01. Score: 2

I believe you could also reduce from bin-packing which is strongly NP-complete according to wikipedia.

Consider this instance of MD-KS:
$$
\max \sum\_{i = 1, j = 1}^{n, m} x\_{i,j} \\
s.t.: \sum\_{j} x\_{i,j} \le 1 \\
\;\;\;\;\;\;\;\; \sum\_{i} a\_{i} x\_{i,j} \le b \\
\;\;\;\;\;\;\;x\_{i, j} \in \{0, 1 \}
$$

The optimization problem above finds the maximum number of objects out of $n$ objects, which can be fit into $m$ bins of size $b$ (size/weight of object $i$) is $a\_i$.

Bin Packing (decision problem): Given $n$ objects, can we fit them in $m$ bins?
Solution: Run optimization above and return true if the optimal value is $n$. False otherwise.

The size of MD-KP here is $mn$ variables and $n + m$ constraints. The size of corresponding bin-packing problem is $n$ objects and $m$ bins. In any case, the sizes are polynomial-ly related so I believe the reduction is valid.

> **Comments:**
> **username_2**: Presumably, @username_0 is trying to show that the problem is strongly NP-hard with a constant number of constraints.  
> **username_7**: For fixed $m$, isn't the original problem polynomial in the length of input? Also, the original problem needs $O(nm)$ coefficients and so does the instance above.  
> **username_2**: If you only wanted to show that the problem is strongly NP-hard for an arbitrary number of ''dimensions'', then yes your reduction works. I think it is more interesting to ask--does it remain strongly NP-hard in 2 or 3 ''dimensions''?  
> **username_7**: There are three lines in this wikipedia article that I find relevant to this discussion. The third line says and I quote "For any fixed m \ge 2, these problems do admit a pseudo-polynomial time algorithm (similar to the one for basic knapsack) and a PTAS.[2]". If this is true, then we the MD-KS is not strongly NP if "m" is a fixed number. Section (Multiple Constraints) of this: http://en.wikipedia.org/wiki/List_of_knapsack_problems  

---

### Answer by username_0 on 2014-04-02. Score: 2

Ok, let me try to answer this myself:

* I was looking for a *reference*, not a proof. My hope was that it is in fact a two-line proof, and that I was just missing that. This seems to be true. The people who saw it, never wrote it up; everybody else just repeated the fact, without seeing the proof, I guess.
* You can use reduction from *any* problem that can be formulated as an ILP with
  + polynomial number of constraints/variables,
  + only non-negative (integer) coefficients in the ILP formulation and objective function,
  + bounded maximum coefficient in the ILP is (either constant or some polynomial in the size of the instance), and
  + all constraints are $\le$.
* Any problem that is NP-hard and *does not involve numbers*, is strongly NP-hard.
* Just as (yet another) example, you can use the ILP formulation of *maximum independent set* as a multidimensional KP, where all coefficients are 0/1. This is the simplest ILP of any problem that I can think of.
* This indeed results in a polynomial number of constraints (polynomial dimension), but:
* For *fixed dimension*, there exists a polynomial *DP* algorithm for finding the best solution; so, it cannot be strongly NP-hard for fixed dimension (@Austin).

Is all of that correct? Then, sorry for the mess. Otherwise, please tell me if/where I am wrong...

> **Comments:**
> **username_2**: A reduction from vertex cover does not work, at least given your statement of multi-dimensional knapsack. The constraints should be of the $\le$ type. Max clique or set packing would work.  
> **username_0**: My fault, thanks. I have replaced vertex cover by maximum independent set, the other side of the coin.  
> **username_4**: Multidimensional knapsack is essentially the same as what are called packing integer programs (PIPs) which captures max independent set as a special case, as you observe.  

---

