[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.