Reduction from SUBSET-SUM to 0-1-INT-PROG

Question

The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.

I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.

My attempt:

Given an instance of SUBSET-SUM $<\{a_1, a_2, \cdots, a_n\}, k>$ we construct an instance of 0-1-INT-PROG $<[a_1, a_2, \cdots, a_n], [k]>$.

Claim: $<\{a_1, a_2, \cdots, a_n\}, k> \in $ SUBSET_SUM if and only if $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.

proof of forward direction. When there exists a subset $S' \subseteq S$ whose sum is $k$, for each $a_i \in S'$, let $x_i = 1$. If $x_i \not \in S'$, then $x_i = 0$. Then $x$ is an $n$-vector which achieves $[a_1, a_2, \cdots, a_n] \cdot x = k$. So $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.

Question:

When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $x$ vector with $[a_1, a_2, \cdots, a_n] \cdot x \leq k$, does not imply that there exists a subset $S' \subseteq S$ whose sum is $k$, because of the less than or equals to.

So how can I approach the backwards direction?

Answer 1

Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\{a_1, a_2, \dots, a_n\}$. Construct an 0ドル$-1ドル$-integer program with $n$ binary variables $x_1, \dots, x_n$ and the following constraints:

$$ \begin{align} a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\ -a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k \end{align} $$

Or, in matrix form: $A = \begin{bmatrix} a_1 & a_2 & \dots & a_n \\ -a_1 & -a_2 & \dots & -a_n \end{bmatrix}$ and $b=\begin{bmatrix} k \\ -k\end{bmatrix}$.

If you have a solution $S' \subseteq S$ to the subset sum instance, then you can pick $x$ as the characteristic vector of $S'$ to satisfy the constraints (as you correctly point out in your question). I.e., set $x_i = 1$ if and only if $a_i \in S'$ so that $Ax = \begin{bmatrix} k \\ -k\end{bmatrix} = b$.

On the other hand, if $Ax \le b$ then the first constraint is $a_1 + a_2 + \dots + a_n \le k$ and second constraint implies $a_1 + a_2 + \dots + a_n \ge k$. Then, we necessarily have $a_1 + a_2 + \dots + a_n = k$, showing that $S' = \{ a_i \mid x_i = 1\}$ is a solution to the subset sum instance.

• Tom Finet: So we add a constraint to satisfy the backward direction. I like it, thank you.