[Model] BinPacking

[GiggleLiu]

Motivation

Classic NP-hard combinatorial optimization problem, widely studied in operations research, scheduling, and resource allocation. Has natural reductions to ILP and QUBO, and a dual relationship with Set Covering (covering item-to-bin assignments vs. covering universe elements).

Definition

Name: BinPacking
Reference: Garey & Johnson, Computers and Intractability, 1979; Martello & Toth, Knapsack Problems, 1990

Given a set of n items with sizes s₁, …, sₙ ∈ R⁺ and a bin capacity C > 0, find an assignment of items to bins such that:

1. Every item is assigned to exactly one bin.
2. For each bin j, the total size of items assigned to bin j does not exceed C: Σ_{i: x_i=j} s_i ≤ C.
3. The number of bins used is minimized.

Variables

• Count: n (one variable per item)
• Per-variable domain: {0, …, n−1} (bin index; worst case is n bins, one item each)
• Meaning: x_i = j means item i is assigned to bin j

Schema (data type)

Type name: BinPacking
Variants: weight type W (i32 default, f64 for real-valued sizes)

Field	Type	Description
sizes	Vec<W>	Item sizes s_i for each item i ∈ {0, …, n−1}
capacity	W	Bin capacity C

Problem Size

Metric	Expression	Description
num_items	n	Number of items to pack

Complexity

• Decision complexity: NP-complete in the strong sense (Garey & Johnson, 1979)
• Best known exact algorithm: O(2^n · poly(n)) via dynamic programming on subsets; practical solvers use branch-and-price
• Best known approximation: First Fit Decreasing (FFD) uses at most (11/9)·OPT + 6/9 bins (Dósa & Sgall, 2013); asymptotic PTAS exists (Fernandez de la Vega & Lueker, 1981)

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming (file ILP reduction rule as separate issue).
• Other, refer to ...

Bruteforce: enumerate all assignments x ∈ {0, …, n−1}^n, check capacity constraints, and minimize the number of distinct bin indices used.

Example Instance

7 items, capacity C = 10:

Item	0	1	2	3	4	5	6
Size	7	5	3	4	6	3	2

Optimal solution: 3 bins.

One optimal assignment: Bin 0 = {item 0 (7), item 5 (3)} = 10, Bin 1 = {item 1 (5), item 3 (4)} = 9, Bin 2 = {item 4 (6), item 2 (3)} = 9, with item 6 (2) fitting in Bin 1 or Bin 2.

For example: x = (0, 1, 2, 1, 2, 0, 1) → Bin 0: 7+3=10, Bin 1: 5+4+2=11 ✗ — too full.

Corrected: x = (0, 1, 2, 1, 2, 0, 2) → Bin 0: 7+3=10 ✓, Bin 1: 5+4=9 ✓, Bin 2: 6+3+2=11 ✗.

x = (0, 1, 2, 1, 2, 0, 1) needs adjustment. Valid assignment: x = (0, 1, 2, 2, 1, 0, 2) → Bin 0: 7+3=10 ✓, Bin 1: 5+6=11 ✗.

Valid optimal: x = (0, 1, 2, 1, 0, 2, 1) → Bin 0: {0,4}=7+6=13 ✗.

Let me use a cleaner example:

Revised example: 6 items, capacity C = 10:

Item	0	1	2	3	4	5
Size	6	6	5	5	4	4

Total size = 30, so at minimum ⌈30/10⌉ = 3 bins.

Optimal: 3 bins.

• Bin 0: {item 0 (6), item 4 (4)} = 10 ✓
• Bin 1: {item 1 (6), item 5 (4)} = 10 ✓
• Bin 2: {item 2 (5), item 3 (5)} = 10 ✓

Assignment vector: x = (0, 1, 2, 2, 0, 1)

This achieves the lower bound ⌈30/10⌉ = 3, so it is provably optimal.

Note: a greedy First Fit approach with unsorted items might yield 4 bins (e.g., assigning in order: Bin 0: 6+4=10, Bin 1: 6, Bin 2: 5+5=10, Bin 3: 4 → item 5 doesn't fit in Bin 1 → 4 bins), demonstrating that the problem is non-trivial.