🧩 Constraint Solving POTD:Problem of the Day: Bin Packing — A Timeless Optimization Challenge

[github-actions[bot]]

Problem Statement

The Bin Packing Problem is a classic optimization challenge: given a collection of items with different sizes and a set of bins with fixed capacity, pack all items into the minimum number of bins.

Concrete Instance

Suppose you have:

• Items: 10 items with weights [7, 5, 8, 6, 4, 9, 3, 5, 7, 6]
• Bin capacity: 15 units
• Goal: Find the minimum number of bins needed to pack all items (no item can be split across bins)

Optimal solution: 5 bins

• Bin 1: [8, 7] = 15
• Bin 2: [9, 6] = 15
• Bin 3: [7, 5] = 12
• Bin 4: [6, 5] = 11
• Bin 5: [4, 3] = 7

Input/Output Specification

Input:

• A set of items I = {1, 2, ..., n} with weights w_i ∈ R+
• Bin capacity C ∈ R+

Output:

• An assignment of items to bins x_{ij} ∈ {0,1} where x_{ij} = 1 if item i is packed in bin j
• The minimum number of bins m needed

---

Why It Matters

Warehouse & Logistics: Distribution centers pack items into trucks, containers, or shipping boxes. Reducing the number of bins lowers transportation costs and storage requirements. A 5% improvement in bin efficiency across thousands of daily shipments yields significant savings.

Cloud Resource Allocation: Virtual machines are packed into physical servers. Minimizing the number of servers reduces energy consumption and hardware costs while improving utilization.

Manufacturing & Cutting Stock: Raw materials (steel sheets, paper rolls) are cut into finished pieces. Minimizing waste (unused material) is equivalent to minimizing the number of raw rolls or sheets needed.

Memory Management: Operating systems pack processes or data into memory pages. Reducing fragmentation and page count improves cache efficiency and system throughput.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Paradigm: Mathematical Programming

Variables:

• y_j ∈ {0,1} — binary variable indicating whether bin j is used
• x_{ij} ∈ {0,1} — binary variable indicating whether item i is packed in bin j

Constraints:

minimize:   Σ_j y_j                    (minimize bins used)
subject to:
  Σ_j x_{ij} = 1           ∀i ∈ I     (each item in exactly one bin)
  Σ_i w_i · x_{ij} ≤ C · y_j  ∀j      (bin capacity + bin activation)
  x_{ij} ∈ {0,1}, y_j ∈ {0,1}

Trade-offs:

• ✓ Exact solutions via branch-and-bound
• ✓ Declarative and flexible — easy to add constraints (e.g., incompatibilities, weight distribution)
• ✗ Scalability issues — becomes difficult for large instances (hundreds of items)

---

Approach 2: Constraint Programming (CP)

Paradigm: Declarative Search

Variables:

• x_i ∈ {1..m} — the bin ID assigned to item i, where m is the maximum possible bins
• n_bins — the actual number of bins used (to minimize)

Constraints:

minimize:   n_bins
subject to:
  global_cardinality(x_1, ..., x_n)  (enforce used bins are consecutive)
  bin_packing(capacity=C, items=[w_1,...,w_n], bins=x)  (global constraint)
  n_bins = max(x_i)  (actual bins used)
  x_i ∈ {1..m}

Trade-offs:

• ✓ Native global constraints (e.g., bin_packing) provide strong propagation
• ✓ Scalable — propagation algorithms prune the search space efficiently
• ✓ Natural problem encoding — items → bins is intuitive
• ✗ Requires access to CP solver (e.g., OR-Tools, Choco, MiniZinc)

---

Approach 3: Local Search Heuristic

Paradigm: Metaheuristic Search

Algorithm sketch:

1. Start with a greedy initial solution (e.g., First Fit Decreasing: sort items, pack largest first)
2. Iteratively move items between bins to reduce the total number used
3. Accept moves that improve the solution; occasionally accept worse moves (simulated annealing, tabu search)
4. Stop after a time limit or plateau

Trade-offs:

• ✓ Fast and practical — finds good solutions for large instances within seconds
• ✓ No license costs — easy to implement from scratch
• ✗ No optimality guarantees — may miss the true optimum
• ✗ Solution quality depends heavily on neighborhood design and parameters

---

Key Techniques

1. Global Constraints & Propagation

The bin_packing global constraint (available in CP solvers) integrates:

• Cardinality propagation: ensures used bins are tracked correctly
• Cumulative reasoning: checks whether remaining items fit in remaining capacity
• Residual capacity bounds: prunes infeasible assignments early

This is far more efficient than encoding bin capacity as individual linear constraints.

2. Symmetry Breaking

Bin packing has inherent symmetry: swapping bin labels doesn't change the solution. Break it with:

• Ordering constraint: enforce first_item(bin_j) < first_item(bin_{j+1}) (lexicographic bin ordering)
• Capacity ordering: require bins to be filled in descending order of weight (FFD heuristic seed)
• Item grouping: group similar-sized items and assign them together

3. Lower Bounds & Heuristics

Strong lower bounds prune the search tree in exact algorithms:

• Continuous lower bound: ⌈ (Σ_i w_i) / C ⌉ (assumes items can be split)
• First Fit Decreasing (FFD) heuristic: sort items descending by weight, pack greedily — often produces near-optimal solutions quickly
• Dual bounds: linear relaxations of ILP formulations provide feasibility pruning

---

Challenge Corner

**For you to think (redacted)

1. Symmetry awareness: The classic bin packing formulation has exponential symmetry (all permutations of bins are equivalent). Can you design symmetry-breaking constraints that reduce search space without removing optimal solutions? What are the trade-offs of different ordering constraints?

2. Online variant: In the online bin packing problem, items arrive one-by-one and must be assigned to a bin immediately (no reassignment). How does this change the problem complexity? Can you design a deterministic online algorithm with a constant approximation ratio?

3. Extension with constraints: Many real applications add side constraints:

   • Items have mandatory pairings (must be in the same bin)
   • Items have incompatibilities (cannot be in the same bin)
   • Bins have non-uniform capacities

   How would you model each of these extensions in your chosen paradigm (ILP, CP, or local search)?

---

References

1. Falkenauer, E. (1996). Genetic Algorithms and Grouping Problems. Wiley. — Classic reference for metaheuristic approaches to bin packing.

2. Coffman Jr., E. G., Garey, M. R., & Johnson, D. S. (1984). "Approximation algorithms for bin packing: an updated survey." In Algorithms and Complexity, pp. 49–106. — Comprehensive survey of approximation results and lower bounds.

3. Shaw, P. (2004). "A constraint for bin packing." In CP 2004: Principles and Practice of Constraint Programming, LNCS 3258, pp. 648–662. — Introduction of the global bin_packing constraint and its propagation algorithm.

4. Pisinger, D., & Sigurd, M. (2005). "Using Dantzig-Wolfe decomposition for large vehicle routing problems." European Journal of Operational Research, 160(2), 459–473. — Column generation techniques applicable to bin packing and related problems.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.16 AIC · ⌖ 4.82 AIC · ⊞ 6.2K · ◷

• expires on Sep 2, 2026, 3:41 AM UTC-08:00