Subset Sum to Integer Linear Programming (Karp Reduction)

Definition

Subset Sum to Integer Linear Programming

There is a polynomial-time many-one reduction from the Subset Sum problem to the decision version of integer linear programming:

$$\mathrm{SUBSET}\mathrm{SUM}{\le }_m^p{\mathrm{ILP}}_{\mathrm{decision}}.$$

Construction

Given a Subset Sum instance with positive integers $p_1,\dots ,p_n$ and target $k$, create one integer variable $x_i$ for each $p_i$. Force every variable to be binary using

$$-x_i\le 0,x_i\le 1(i=1,\dots ,n).$$

Encode the target equality with two inequalities:

$$\sum _{i=1}^n{p}_i{x}_i\le k,-\sum _{i=1}^n{p}_i{x}_i\le -k.$$

Finally, use the zero objective and target

$$c=(0,\dots ,0),t=0.$$

Correctness

The subset sum instance is a yes-instance if and only if the constructed ILP instance is a yes-instance.

Correctness

Forward $I\subseteq \{1,\dots ,n\}$ satisfies

If an index set

$$\sum _{i\in I}{p}_i=k,$$

set $x_i=1$ for $i\in I$ and $x_i=0$ otherwise. All constraints hold, and the objective reaches $t=0$.

Backward $0\le x_i\le 1$, hence $x_i\in \{0,1\}$. For

Any feasible integer assignment satisfies

$$I=\{i:x_i=1\},$$

the two weighted inequalities imply

$$\sum _{i\in I}{p}_i=k.$$

Thus, $I$ is a Subset Sum solution.

Running time

The reduction creates $n$ variables and $2n+2$ inequalities. It copies only the input coefficients $p_i$ and $k$, so its running time and output encoding size are polynomial in the input size.

NP-hardness

Since Subset Sum is NP-hard, the reduction proves that ILP is NP-hard. It does not by itself prove strong NP-hardness because the coefficients $p_i$ may be exponentially large relative to their binary encodings; see A Reduction Transfers Hardness, Not Weakness.