[Rule] Knapsack to ILP

[GiggleLiu]

Source

Knapsack

Target

ILP (Integer Linear Programming)

Motivation

• Connects the orphan Knapsack problem to the main reduction graph (ILP has 13 inbound reductions)
• Enables solving Knapsack instances using any ILP solver
• Classic, well-known textbook reduction

Reference

Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall. (Section on Integer Programming formulations of combinatorial problems)

Reduction Algorithm

Given a Knapsack instance with n items, weights $w_1, \ldots, w_n$, values $v_1, \ldots, v_n$, and capacity $C$:

1. Create $n$ binary variables $x_1, \ldots, x_n$, where $x_i = 1$ means item $i$ is selected.
2. Set the objective function to maximize $v_1 x_1 + v_2 x_2 + \cdots + v_n x_n$.
3. Add one constraint: $w_1 x_1 + w_2 x_2 + \cdots + w_n x_n \le C$.
4. Each variable is bounded: $0 \le x_i \le 1$ (binary).

Solution extraction: The binary vector $(x_1, \ldots, x_n)$ directly maps back — item $i$ is selected if $x_i = 1$.

Size Overhead

Target metric	Formula
num_vars	num_items
num_constraints	1

Validation Method

Closed-loop test: construct a Knapsack instance, reduce to ILP, solve ILP with brute force, extract solution back to Knapsack, and verify optimality.

Example

Source (Knapsack): 4 items, weights = (1, 3, 4, 5), values = (1, 4, 5, 7), capacity = 7.

Target (ILP):

• Variables: $x_1, x_2, x_3, x_4 \in {0, 1}$
• Maximize: $x_1 + 4x_2 + 5x_3 + 7x_4$
• Subject to: $x_1 + 3x_2 + 4x_3 + 5x_4 \le 7$

Optimal ILP solution: $(0, 1, 1, 0)$ with objective value 9.
Extracted Knapsack solution: Select items 2 and 3, total weight = 7, total value = 9.

This example is non-trivial because a greedy-by-value approach would pick item 4 (highest value = 7), leaving only room for item 1, yielding value = 8 < 9.

[GiggleLiu]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from Knapsack to ILP; connects orphan to main graph
Non-trivial	✅ Pass	Constructs ILP with objective + constraint from knapsack items; also connects disconnected problem
Correctness	✅ Pass	Papadimitriou & Steiglitz (1982) is a well-known textbook; reduction is a standard formulation
Well-written	⚠️ Warn	Overhead table uses num_variables but ILP's actual size field is num_vars

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

No reduction path exists from Knapsack to any other problem — Knapsack is currently an orphan (0 inbound, 0 outbound). This reduction connects it to ILP, which is the largest hub in the graph (13 inbound reductions, 2 outbound). Novel and high-value.

Non-trivial

The reduction constructs a new ILP instance: binary variables for item selection, a linear objective from values, and a capacity constraint from weights. While the mapping is natural, it involves genuine structural transformation (items → variables, knapsack constraint → linear inequality). Additionally, per project rules, even a simple reduction that connects a disconnected problem is considered non-trivial.

Correctness

• Papadimitriou & Steiglitz (1982) — Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall. This is one of the most cited textbooks in combinatorial optimization. The Knapsack-to-ILP formulation is standard material.
• Cross-reference: Garey & Johnson (1979) lists both Knapsack (Convert a problem to QUBO problem #18) and 0-1 Integer Programming (Implement remaining reduction rules #2) among Karp's 21 NP-complete problems. The ILP formulation of Knapsack is a textbook construction appearing in virtually every OR/optimization textbook.
• The mathematical correctness of the reduction is straightforward to verify: feasibility and optimality are preserved by construction.

Note: Papadimitriou & Steiglitz is not yet in docs/paper/references.bib — the implementer should add it.

Well-written

Sections present: ✅ Source, ✅ Target, ✅ Motivation, ✅ Reference, ✅ Reduction Algorithm, ✅ Size Overhead, ✅ Validation Method, ✅ Example

Issue found:

• The overhead table uses num_variables but ILP's actual size field (from pred show ILP --json) is num_vars. This should be corrected to num_vars to match the target problem's getter method. Similarly, verify that num_items matches the Knapsack getter (confirmed: Knapsack::num_items() exists at src/models/misc/knapsack.rs:86).

Example quality: Good. 4 items with a non-greedy optimum that demonstrates the reduction meaningfully. Fully worked with source instance, ILP construction, and extracted solution.

Algorithm quality: Complete, step-by-step, all symbols defined. Solution extraction is clear.

Recommendations

• Fix num_variables → num_vars in the overhead table before implementation
• Add Papadimitriou & Steiglitz to references.bib during implementation