[Rule] BinPacking to ILP

[GiggleLiu]

Source: BinPacking
Target: ILP
Motivation: Enable exact solving of bin packing instances via ILP solvers, following the standard assignment-based formulation.
Reference: Martello & Toth, "Knapsack Problems" (1990), Ch. 8; also standard in most combinatorial optimization textbooks (e.g., Wolsey, "Integer Programming", 2020).

Reduction Algorithm

Notation:

• Source: n items with weights w_1, …, w_n and bin capacity C
• Target: ILP with binary variables, linear constraints, and a minimize objective

Variable mapping:

• x_{ij} ∈ {0, 1} for i = 0, …, n−1 and j = 0, …, n−1: item i is assigned to bin j
• y_j ∈ {0, 1} for j = 0, …, n−1: bin j is used

Total: n² + n binary variables. Variable ordering: x_{00}, x_{01}, …, x_{0,n−1}, x_{10}, …, x_{n−1,n−1}, y_0, …, y_{n−1}.

Constraints:

1. Assignment (each item in exactly one bin): for each item i,
   ∑_j x_{ij} = 1
2. Capacity + linking (bin capacity respected; y_j forced to 1 if bin j is used): for each bin j,
   ∑_i w_i · x_{ij} ≤ C · y_j

Total: 2n constraints.

Objective: minimize ∑_j y_j

Solution extraction: For each item i, find the unique j with x_{ij} = 1; assign item i to bin j.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	n² + n where n = num_items
num_constraints	2n

Validation Method

Closed-loop testing: solve BinPacking with BruteForce, solve the reduced ILP with the ILP solver, and verify the objectives match. Test on multiple instances including edge cases (single item, all items same weight, items that exactly fill bins).

Example

Source instance: 5 items, weights [6, 5, 5, 4, 3], capacity 10.

• Total weight = 23, lower bound = ⌈23/10⌉ = 3 bins
• Optimal: 3 bins, e.g., {6, 4}, {5, 5}, {3} or {6, 3}, {5, 5}, {4}

ILP formulation:

• 30 variables: 25 assignment variables x_{ij} (5×5) + 5 bin-open variables y_j
• 10 constraints: 5 assignment + 5 capacity
• Objective: minimize y_0 + y_1 + y_2 + y_3 + y_4

Optimal ILP solution: objective = 3 (3 bins used). Extracting x_{ij} values gives a valid packing matching the brute-force optimum.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from BinPacking to ILP
Non-trivial	✅ Pass	n²+n variables, assignment + capacity-linking constraints
Correctness	✅ Pass	Both references verified
Well-written	✅ Pass	Complete algorithm, consistent symbols, good example

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

BinPacking currently has zero outgoing reductions. This would be the first, connecting it to ILP and enabling exact solving via ILP solvers.

Non-trivial

Creates n²+n binary ILP variables (xᵢⱼ assignment matrix + yⱼ bin-open indicators) with two families of linear constraints. Solution extraction requires scanning the assignment matrix. Not a variable substitution or identity.

Correctness

Reference	Status	Notes
Martello & Toth (1990), "Knapsack Problems", Ch. 8	✅ Verified	Wiley, ISBN 0471924202. Standard reference for bin packing ILP formulations.
Wolsey (2020), "Integer Programming", 2nd ed.	✅ Verified	Wiley, ISBN 9781119606536. Standard combinatorial optimization textbook.

The assignment-based ILP formulation is the canonical textbook formulation. Variable/constraint counts (n²+n vars, 2n constraints) verified correct.

Well-written

All sections complete. Algorithm is step-by-step and implementable. Overhead metrics num_vars and num_constraints match ILP's size_fields. Example (5 items, capacity 10) is non-trivial and fully worked.

Minor note: The issue uses "weights" (wᵢ) for item sizes, while the BinPacking model uses "sizes" field — cosmetic terminology difference only.