[Rule] Knapsack to ILP

[zazabap]

Source: Knapsack
Target: ILP
Motivation: Enables solving Knapsack via ILP solvers; the most direct formulation since Knapsack is a single-constraint ILP.
Reference: Kellerer, Pferschy & Pisinger, Knapsack Problems, 2004, Ch. 12

Reduction Algorithm

Notation:

• Source: $n$ items with weights $w_0, \ldots, w_{n-1}$, values $v_0, \ldots, v_{n-1}$, capacity $C$
• Target: ILP with binary variables, one linear constraint, and a maximize objective

Variable mapping:

$$x_i \in {0, 1} \quad \text{for } i = 0, \ldots, n-1$$

Each Knapsack variable maps directly to an ILP variable (identity mapping).

Constraint:

$$\sum_{i=0}^{n-1} w_i \cdot x_i \leq C$$

Objective:

$$\text{maximize} \sum_{i=0}^{n-1} v_i \cdot x_i$$

Solution extraction: The ILP solution $x$ is directly the Knapsack solution — no transformation needed.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$n$
num_constraints	$1$

Validation Method

Closed-loop testing: solve Knapsack by brute-force ($2^n$ enumeration), solve the reduced ILP, and verify that both give the same optimal value. Test with edge cases: all items fit, no items fit, single item, items with equal value/weight ratios.

Example

Source instance: $n = 4$ items, capacity $C = 7$.

Item	Weight	Value
0	2	3
1	3	4
2	4	5
3	5	7

ILP formulation:

• 4 binary variables: $x_0, x_1, x_2, x_3$
• 1 constraint: $2x_0 + 3x_1 + 4x_2 + 5x_3 \leq 7$
• Objective: maximize $3x_0 + 4x_1 + 5x_2 + 7x_3$

Optimal ILP solution: $x = (1, 0, 0, 1)$, objective $= 10$.

Extracted Knapsack solution: select items ${0, 3}$, weight $= 7 \leq 7$, value $= 10$, matching brute-force optimum.

[zazabap]

Closing: this reduction is near-trivial (Knapsack is essentially a single-constraint ILP). Replaced with a higher-value cross-domain reduction (3SAT → SubsetSum).