[Rule] IntegerKnapsack to ILP

[isPANN]

Source

IntegerKnapsack — unbounded knapsack with integer multiplicities

Target

ILP (Integer Linear Programming, variable: "int" variant)

Motivation

Direct ILP formulation for IntegerKnapsack. The unbounded knapsack problem has a natural ILP encoding: one integer variable per item representing the multiplicity, a single capacity constraint, and a linear objective. This provides an exact solver path via ILP solvers (e.g., HiGHS) and complements the brute-force solver for correctness verification.

Companion to #532 ([Model] IntegerKnapsack).

Reference

Standard ILP formulation of the unbounded knapsack problem. See any operations research textbook, e.g., Wolsey, Integer Programming (2020), Ch. 1.

Reduction Algorithm

Given an IntegerKnapsack instance with items U = {u₁, ..., uₙ}, sizes s(uᵢ), values v(uᵢ), and capacity B:

1. Variables: Create n integer variables c₁, ..., cₙ with cᵢ ≥ 0 for each item uᵢ. Upper bound: cᵢ ≤ floor(B / s(uᵢ)).
2. Constraint: Add one constraint: Σᵢ s(uᵢ) · cᵢ ≤ B.
3. Objective: Maximize Σᵢ v(uᵢ) · cᵢ.
4. Solution extraction: The ILP solution gives the multiplicity vector c directly — each cᵢ is the number of times item uᵢ is used.

Size Overhead

Target metric (code name)	Formula
num_vars	num_items
num_constraints	1

Validation Method

Closed-loop test: construct an IntegerKnapsack instance, reduce to ILP, solve ILP, extract solution, verify it is optimal for the original instance (compare against brute-force).

Example

Source (IntegerKnapsack):
sizes = [3, 4, 5, 2, 7], values = [4, 5, 7, 3, 9], capacity = 15

Target (ILP):
Variables: c₁, c₂, c₃, c₄, c₅ ∈ Z≥0 (with bounds c₁≤5, c₂≤3, c₃≤3, c₄≤7, c₅≤2)
Constraint: 3c₁ + 4c₂ + 5c₃ + 2c₄ + 7c₅ ≤ 15
Objective: maximize 4c₁ + 5c₂ + 7c₃ + 3c₄ + 9c₅

Optimal: c = (0, 0, 1, 5, 0), value = 22.