🧩 Constraint Solving POTD:Bin Packing — minimise the number of bins

[github-actions[bot]]

🗂️ Problem of the Day — Bin Packing

Problem Statement

You have n items, each with a weight w_i, and an unlimited supply of bins each with capacity C. The goal is to pack all items into the fewest bins possible.

Concrete Instance (8 items, capacity = 10)

Item	1	2	3	4	5	6	7	8
Weight	6	3	5	4	2	7	4	3

Optimal solution uses 4 bins:

• Bin 1: {1, 5} → 6+2 = 8
• Bin 2: {2, 4, 8} → 3+4+3 = 10
• Bin 3: {3, 7} → 5+4 = 9
• Bin 4: {6} → 7

Input: item weights w_1, ..., w_n and bin capacity C
Output: minimum number of bins k and an assignment bin(i) ∈ {1..k} for each item

---

Why It Matters

• Cloud computing: Assigning virtual machines (with CPU/RAM demands) to physical servers minimises infrastructure cost — every saved server is direct revenue.
• Logistics & packaging: Minimising the number of trucks, shipping containers, or cartons reduces transport cost and carbon footprint in supply chain operations.
• Compiler register allocation: Assigning variables to a fixed set of CPU registers is equivalent to bin packing with additional interference constraints.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables:

• bin(i) ∈ {1..n} — bin assigned to item i
• k — number of bins used (minimise)

Key constraints:

∀ b ∈ 1..k:  sum(w_i | bin(i) = b) ≤ C    // capacity
bin(i) ≤ k   ∀i                            // items fit in range

Global constraint: bin_packing_capa(load, bin, w) (available in most CP solvers) computes the load on each bin via a single propagator — far stronger than decomposing into sums.

Trade-offs: Excellent propagation via the global constraint; symmetry among bins must be broken explicitly or search explodes.

Approach 2 — Mixed Integer Programming (MIP)

Decision variables:

• y_j ∈ {0,1} — bin j is used
• x_ij ∈ {0,1} — item i is in bin j

Model:

Minimise  ∑_j y_j
s.t.      ∑_j x_ij = 1          ∀ i          // each item assigned once
          ∑_i w_i · x_ij ≤ C · y_j  ∀ j      // capacity only if bin open
          x_ij ≤ y_j              ∀ i,j
          x_ij, y_j ∈ {0,1}

Trade-offs: LP relaxation gives a useful lower bound (∑w_i / C); scales to large instances with branch-and-bound + column generation; less natural for expressing ordering symmetry.

Example Model — MiniZinc (CP)

include "bin_packing_capa.mzn";

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

int: max_bins = n;
array[1..max_bins] of var 0..C: load;   % load per bin
array[1..n]        of var 1..max_bins: bin;  % bin for each item
var 1..max_bins: k = max(bin);           % bins used

constraint bin_packing_capa(load, bin, w);

% Symmetry breaking: items ordered by weight, bins used in order
constraint forall(i in 1..n-1)(w[i] >= w[i+1] -> bin[i] <= bin[i+1]);

solve minimize k;

output ["k = \(k)\n", "bin = \(bin)\n"];

---

Key Techniques

1. The bin_packing_capa Global Constraint

This single propagator simultaneously enforces capacity limits on all bins and filters bin(i) values by checking whether item i can feasibly be placed anywhere. It achieves bounds consistency in O(n log n) time — vastly better than a sum-decomposition.

2. Symmetry Breaking

Bins are interchangeable: swapping items between bin 1 and bin 2 gives an equivalent solution but blows up the search space. Common fixes:

• Lexicographic ordering: require bin(i) ≤ bin(i+1) when w_i = w_{i+1}
• First-fit decreasing (FFD) seed: order items by decreasing weight before assigning; FFD produces a feasible solution provably within 11/9 · OPT + 6/9 bins and acts as a warm start
• Value ordering: always try the lowest-indexed open bin first (First Fit heuristic)

3. Column Generation for MIP

The MIP formulation above has O(n2) binary variables. Column generation (Gilmore–Gomory, 1961) works over the exponentially many feasible packing patterns instead. The restricted master problem has far fewer variables at any time; new columns are generated by solving a bounded knapsack subproblem. This is the method of choice for industrial-scale instances (n > 10 000).

---

Challenge Corner

Extension: Suppose bins come in two sizes — small (capacity 8) and large (capacity 15) — with different costs. How would you modify the CP or MIP model to minimise total cost rather than number of bins? Can you think of a greedy heuristic that achieves a provable approximation ratio for this heterogeneous variant?

---

References

1. Martello & Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. — The classical reference covering exact and heuristic methods for bin packing.
2. Coffman, Garey & Johnson (1997). "Approximation algorithms for bin packing: A survey." In Approximation Algorithms for NP-Hard Problems, PWS Publishing. — Comprehensive survey of worst-case guarantees for greedy algorithms.
3. Trick (2003). "A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints." CPAIOR 2003. — Foundation for modern CP propagators including bin_packing_capa.
4. MiniZinc Handbook — [bin_packing_capa documentation]((www.minizinc.org/redacted) with worked examples and solver hints.

Generated by 🧩 Constraint Solving — Problem of the Day · ● 2M · ◷

• expires on May 22, 2026, 12:06 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 #32609.