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.
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:
Variable mapping:
Each Knapsack variable maps directly to an ILP variable (identity mapping).
Constraint:
Objective:
Solution extraction: The ILP solution$x$ is directly the Knapsack solution — no transformation needed.
Size Overhead
num_varsnum_constraintsValidation 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$ .
ILP formulation:
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.