🧩 Constraint Solving POTD:Bin Packing — 2026-03-30

[github-actions[bot]]

Category: Packing & Cutting · Date: 2026-03-30

---

Problem Statement

You have a collection of items, each with a known size, and an unlimited supply of identical bins, each with a fixed capacity. The goal is to pack all items into the fewest bins possible.

Formal specification

• n items, item i has size s_i ∈ (0, 1] (normalized to bin capacity = 1)
• Up to n bins available (worst case: one item per bin)
• x_{ij} = 1 if item i is placed in bin j; y_j = 1 if bin j is used
• Minimize: ∑_j y_j
• Subject to: each item in exactly one bin; no bin exceeds capacity

Small concrete instance (5 items, capacity = 10)

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

One optimal packing uses 2 bins: {2, 3} (sizes 7+3=10) and {1, 4, 5} (sizes 4+6... wait, 4+6=10, +2=12 ❌). Better: {2, 3} and {1, 5} (6) and {4} (6) — 3 bins, or {2, 3} and {4, 5} (8) and {1} — still 3 bins. Lower bound: ⌈(4+7+3+6+2)/10⌉ = ⌈22/10⌉ = 3 bins. Optimal = 3.

---

Why It Matters

Cloud resource allocation — Virtual machines of varying memory/CPU requirements must be packed onto physical hosts to minimize the number of active servers, directly reducing operational costs.

Freight and logistics — Shipping containers, trucks, and cargo holds must be loaded efficiently; bin packing captures the 1-D capacity version of a ubiquitous daily optimization.

Compiler register allocation — Live variable ranges are "items" to be packed into a fixed set of CPU registers (the "bins"), making bin packing central to code generation.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables

• bin[i] ∈ {1..n} — which bin item i goes into
• load[j] ∈ {0..C} — total load in bin j (implied, linked via bin_packing global)

Key constraints

∀j: load[j] = ∑_{i: bin[i]=j} s_i          // bin capacity
∀j: load[j] ≤ C                              // feasibility
load[1] ≥ load[2] ≥ ... ≥ load[n]            // symmetry breaking (sorted bins)
```
**Objective:** minimize the index of the last non-empty bin (or equivalently, `max{j : load[j] > 0}`).

**Trade-offs:** The `bin_packing` global constraint provides strong domain filtering (e.g., via energy reasoning). Symmetry breaking on bin order dramatically reduces search, but the encoding still has `O(n²)` propagation in the worst case for large instances.

---

#### Approach 2 — Mixed-Integer Programming (MIP)

**Decision variables**
- `x_{ij} ∈ {0,1}` — item `i` assigned to bin `j`
- `y_j ∈ {0,1}` — bin `j` is used

**Formulation**
```
Minimize   ∑_j y_j
Subject to ∑_j x_{ij} = 1           ∀i    (each item assigned once)
           ∑_i s_i · x_{ij} ≤ C·y_j  ∀j    (capacity & bin activation)
           y_j ≥ y_{j+1}              ∀j    (symmetry breaking: pack in order)
           x_{ij}, y_j ∈ {0,1}

Trade-offs: Tight LP relaxations via cutting planes (e.g., cover inequalities) make branch-and-bound effective for moderate instances. However, the O(n²) binary variables scale poorly for large n; column generation (set-cover reformulation) is the industrial-strength remedy.

---

Example Model — MiniZinc (CP)

include "globals.mzn";

int: n = 5;
int: C = 10;
array[1..n] of int: s = [4, 7, 3, 6, 2];

array[1..n] of var 1..n: bin;        % which bin each item goes in
array[1..n] of var 0..C: load;       % load per bin

constraint bin_packing_load(load, bin, s);
constraint forall(j in 1..n)(load[j] <= C);

% Symmetry breaking: bins used in order
constraint forall(j in 1..n-1)(load[j] >= load[j+1]);

var 1..n: num_bins = max(j in 1..n)(bin[j]);
solve minimize num_bins;

output ["Bins used: ", show(num_bins), "\n",
        "Assignment: ", show(bin), "\n"];

---

Key Techniques

1. Energy-Based Lower Bounds

The classic lower bound ⌈∑ s_i / C⌉ is often weak. Dual-feasible functions (DFFs) transform item sizes to tighter lower bounds without changing the feasibility structure. The Floorceiling bound is a well-known DFF-based improvement. These bounds guide both branch-and-bound and CP search.

2. The bin_packing Global Constraint

CP solvers expose bin_packing (and bin_packing_load) as a global constraint. Internally it applies knapsack-based filtering: for each bin, it checks whether the remaining "slack" can accommodate subsets of unassigned items, pruning bin[i] domains accordingly. This is exponentially stronger than decomposing into element/sum constraints.

3. First-Fit Decreasing (FFD) Heuristic + Symmetry Breaking

FFD — sort items by decreasing size and greedily pack each into the first bin with room — runs in O(n log n) and guarantees ≤ 11/9 · OPT + 6/9 bins. In exact solvers, FFD gives an upper bound to seed branch-and-bound. Pairing FFD with the symmetry-breaking constraint load[1] ≥ load[2] ≥ ... eliminates the vast majority of symmetric optima, often reducing search by orders of magnitude.

---

Challenge Corner

Extension: The Vector Bin Packing problem generalizes bin packing to d dimensions — each item has a d-dimensional size vector (e.g., RAM and CPU) and each bin has a capacity in every dimension. How would you adapt the MIP formulation and the bin_packing global for two-dimensional resource constraints? Can the FFD lower bound argument be extended, and if so, what approximation ratio do you get?

---

References

1. Martello & Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley — foundational coverage of bin packing algorithms and lower bounds.
2. Coffman, Garey & Johnson (1997). "Approximation algorithms for bin packing: A survey." In Approximation Algorithms for Combinatorial Optimization Problems, pp. 46–93 — comprehensive survey of FFD and related guarantees.
3. Shaw (2004). "A constraint for bin packing." Proceedings of CP 2004, Springer — introduces the bin_packing global constraint with knapsack-based filtering.
4. Delorme, Iori & Martello (2016). "Bin packing and cutting stock problems: Mathematical models and exact algorithms." European Journal of Operational Research, 255(1):1–20 — modern MIP and exact methods review.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 6, 2026, 12:55 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #23705.