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:

Construction

Given a Subset Sum instance with positive integers and target , create one integer variable for each . Force every variable to be binary using

Encode the target equality with two inequalities:

Finally, use the zero objective and target

Correctness

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

Correctness

Forward

If an index set satisfies

set for and otherwise. All constraints hold, and the objective reaches .

Backward

Any feasible integer assignment satisfies , hence . For

the two weighted inequalities imply

Thus, is a Subset Sum solution.

Running time

The reduction creates variables and inequalities. It copies only the input coefficients and , 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 may be exponentially large relative to their binary encodings; see A Reduction Transfers Hardness, Not Weakness.