🧩 Constraint Solving POTD:Problem of the Day: Bin Packing

[github-actions[bot]]

Problem Statement

You have n items with sizes w1, w2, ..., wn and m bins with equal capacity C. Your goal is to pack all items into the minimum number of bins such that the total size of items in each bin does not exceed its capacity.

Small Concrete Example:

• Items: sizes [6, 8, 3, 5, 7, 4] (6 items)
• Bin capacity: C = 10
• Optimal packing (4 bins): {6,4}, {7,3}, {8}, {5}

Input/Output:

• Input: Item sizes and bin capacity
• Output: Assignment of each item to a bin, minimizing the number of bins used

---

Why It Matters

Warehouse & Logistics: Companies like Amazon and DHL solve bin packing daily to minimize shipping containers, trucks, and storage space. Reducing bins by 5% saves millions in transportation costs.

Memory Allocation: Operating systems use bin packing algorithms to allocate memory pages to reduce fragmentation and improve cache efficiency.

Cloud Resource Scheduling: Virtual machine provisioning across physical servers is a bin packing variant—packing VMs into servers to minimize energy consumption and data center utilization.

Manufacturing & Cutting Stock: Paper mills, glass cutters, and textile manufacturers face cutting stock problems—minimizing waste by optimally cutting rolls or sheets into required pieces.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP) – Flow-Based

Decision Variables:

• x[i][j] ∈ {0, 1}: Item i is assigned to bin j
• y[j] ∈ {0, 1}: Bin j is used (has at least one item)

Constraints:

Minimize: Σj y[j]

Subject to:
  Σj x[i][j] = 1                    ∀i (each item assigned to exactly one bin)
  Σi wi·x[i][j] ≤ C·y[j]            ∀j (bin capacity respected)
  x[i][j] ∈ {0,1}                   ∀i,j
  y[j] ∈ {0,1}                      ∀j

Trade-offs: Straightforward, works for small instances (~100 items). Solves to optimality but slow for larger instances.

---

Approach 2: Constraint Programming (CP) – Symbolic

Decision Variables:

• bin[i] ∈ [1..m]: Bin assigned to item i
• load[j] ∈ [0..C]: Total load of bin j
• max_bin ∈ [1..m]: Maximum bin index used

Constraints:

Minimize: max_bin

Subject to:
  load[j] = Σ{i: bin[i]=j} wi      ∀j (load computation)
  load[j] ≤ C                       ∀j (capacity)
  max_bin ≥ bin[i]                  ∀i (track highest-indexed bin)
  bin[i] ∈ [1..m]                   ∀i

Trade-offs: Global constraints enable stronger propagation. Better scaling than ILP for medium instances. Supports symmetry-breaking naturally.

---

Approach 3: Local Search / Metaheuristics

Heuristic: First-Fit Decreasing (FFD)

1. Sort items by size in descending order
2. For each item, place it in the first bin with sufficient space
3. If no bin has space, open a new bin

FFD(items, capacity):
  sort items descending by size
  bins = []
  for item in items:
    for bin in bins:
      if bin.load + item.size ≤ capacity:
        bin.add(item)
        continue to next item
    bins.append(new Bin with item)
  return bins.length

Trade-offs: FFD achieves ~11/9 OPT (within 11/9 times optimal). Fast (O(n log n)) and scales to thousands of items. No guarantee of optimality but excellent practical performance.

---

Example MiniZinc Model

int: n = 6;                              % number of items
int: m = 10;                             % max bins (upper bound)
int: C = 10;                             % bin capacity
array[1..n] of int: w = [6,8,3,5,7,4];  % item weights

% Decision variables
array[1..n] of var 1..m: bin;            % bin assignment for each item
array[1..m] of var 0..C: load;           % total load per bin
var 1..m: num_bins;                      % number of bins used

% Constraints
constraint forall(j in 1..m) (
  load[j] = sum(i in 1..n where bin[i]=j) (w[i])
);

constraint forall(j in 1..m) (
  load[j] <= C
);

constraint num_bins = max(i in 1..n) (bin[i]);

% Symmetry-breaking: bins are used in order
constraint forall(j in 2..m) (
  load[j-1] > 0 \/ load[j] = 0
);

solve minimize num_bins;

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

---

Key Techniques

1. First-Fit Decreasing (FFD) Heuristic

Sort items by size in decreasing order, then greedily pack into the first available bin. This heuristic guarantees a solution within 7⁄8 of the theoretical lower bound and is the baseline for most practical applications.

2. Lower Bounds & Relaxations

• Trivial bound: ⌈Σwi / C⌉ (sum of sizes divided by capacity)
• LP relaxation: Relax assignments to continuous [0,1]; optimal LP value provides a lower bound
• Branch-and-bound: Prune branches where LB ≥ current best solution

3. Constraint Propagation & Global Constraints

• Bin load reasoning: Preprocess to detect items that must go together
• Symmetry-breaking: Impose ordering load[1] ≥ load[2] ≥ ... ≥ load[m]
• Arc consistency: Reduce variable domains through constraint propagation

4. Variable Ordering Heuristics

• Largest-first: Branch on largest items first
• Minimum load bin heuristic: Assign items to bins with lowest current load
• Impact-based search: Prioritize items whose assignment most constrains the remaining problem

---

Challenge Corner

Question for Reflection:

1. Symmetry Breaking: The naive model has m! symmetries (permutations of bins). Design three different symmetry-breaking constraints:

   • Ordering by load (e.g., load[1] ≥ load[2] ≥ ...)
   • Ordering by smallest item in each bin
   • Channel to a "next" variable array

2. Online vs. Offline: In the online variant, items arrive one at a time. How does FFD perform compared to the offline optimum? Research the competitive ratio.

3. Multi-Capacity Bins: Extend the model to handle bins of different capacities. What new heuristics would you introduce?

---

References

1. Coffman Jr., E. G., et al. (2013). "Bin Packing Approximation Algorithms: Survey and Classification." In Handbook of Combinatorial Optimization (pp. 455–531). — Comprehensive survey covering approximation ratios and variants.

2. Rossi, F., Van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. Chapter on global constraints and packing problems.

3. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer. — Branch-and-bound with constraint propagation.

4. MiniZinc: (www.minizinc.org/redacted) — Bin packing model library and benchmarks.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 37.5K · ◷

• expires on Jun 10, 2026, 12:58 PM UTC