🧩 Constraint Solving POTD:Problem of the Day: Online Bin Packing and the Worst-Fit Decreasing Heuristic

[github-actions[bot]]

Problem Statement

Online Bin Packing is a dynamic variant of the classic bin packing problem where items arrive sequentially, and you must assign each item to a bin immediately before seeing future items.

Concrete Instance

Suppose you manage a warehouse with bins of capacity 10 units. Items arrive one by one:

• Item A (size 6)
• Item B (size 5)
• Item C (size 3)
• Item D (size 4)
• Item E (size 7)

You must decide which bin each item goes into the moment it arrives, without knowing future items. Can you pack them efficiently?

Input/Output Specification

• Input: A sequence of items with sizes s_1, s_2, ..., s_n and a bin capacity C.
• Output: An assignment of items to bins such that:
  • Each item is assigned to exactly one bin
  • The total size of items in each bin ≤ C
  • The number of bins used is minimized (or stays within target bounds)
  • Constraint: Decisions are irreversible once made

---

Why It Matters

Memory and storage management: Operating systems use online bin packing to allocate memory pages to physical memory blocks, deciding immediately where to place each incoming page without preemption.

Logistics and delivery routing: Courier services pack parcels into trucks as orders arrive in real-time. Repacking is expensive, so online assignment strategies matter.

Data center resource scheduling: Cloud providers assign incoming compute jobs to servers on arrival, balancing workloads without ability to migrate past assignments retrospectively.

Manufacturing job scheduling: Production systems assign incoming jobs to machines based on current state, minimizing idle time and setup costs.

---

Modeling Approaches

Approach 1: Greedy Online Algorithm (Heuristic)

Paradigm: Local search / greedy heuristic (not a formal constraint model, but a practical online strategy).

Key idea: Use a simple rule at each arrival to decide bin placement:

• First Fit (FF): Place item in the first bin with enough space; if none exist, open a new bin.
• Best Fit (BF): Place item in the bin with least remaining capacity (tightest fit).
• Worst Fit (WF): Place item in the bin with most remaining capacity (preserve flexibility).

Decision mechanism (pseudo-code for Worst-Fit Decreasing):

Sort items by size (descending)
For each item i with size s_i:
  bins_with_space = [b for b in bins if remaining_capacity[b] >= s_i]
  if bins_with_space is empty:
    create new bin
    assign item to new bin
  else:
    best_bin = argmax(remaining_capacity[b] for b in bins_with_space)
    assign item to best_bin
    remaining_capacity[best_bin] -= s_i

Trade-offs:

• ✅ Low computational cost (linear or O(n log n) with sorting)
• ✅ No lookahead; works with truly online arrivals
• ❌ No optimality guarantees; solution quality depends on arrival order
• ❌ Greedy decisions may miss global structure

Approach 2: Constraint Programming with Relaxed Lookahead

Paradigm: Constraint Programming (CP) with predictive simulation.

Key idea: Maintain a constraint model of current bin assignments plus a buffer of predicted future items. At each arrival:

Decision variables:

• x_i ∈ {1, ..., B} = bin assignment for item i
• load[b] ∈ Z+ = total load in bin b
• open[b] ∈ {0, 1} = whether bin b is in use

Constraints:

∀ i ∈ items:  x_i is assigned
∀ b ∈ bins:   load[b] = Σ(s_i where x_i = b)
∀ b ∈ bins:   load[b] ≤ C
∀ b ∈ bins:   open[b] = 1 iff load[b] > 0
Minimize:      Σ(open[b] for b in bins)

With a lookahead window, try to find assignments that leave room for predicted near-future items. Use constraint propagation (domain consistency) to prune infeasible choices early.

Trade-offs:

• ✅ Can incorporate predictions; more strategic than pure greedy
• ✅ Constraint propagation detects conflicts early
• ✅ Explore multiple assignments with search
• ❌ Requires computational overhead; not strictly online if lookahead is large
• ❌ Model quality depends on prediction accuracy

Approach 3: Reinforcement Learning Policy (Emerging)

Paradigm: ML-guided search with constraint feedback.

Key idea: Train a neural network policy that learns to choose bins conditioned on:

• Current item size
• Histogram of remaining capacities across open bins
• Past assignment history

The policy outputs a probability distribution over bin choices; constraints validate and prune infeasible actions.

Trade-offs:

• ✅ Can learn good heuristics from offline data
• ✅ Adaptive to specific problem distributions
• ❌ Requires offline training; cold-start is poor
• ❌ "Black box" decisions harder to debug or explain
• ❌ Constraint safety must be enforced explicitly

---

Key Techniques

1. Competitive Analysis & Approximation Ratios

Online bin packing has proven worst-case bounds: First Fit Decreasing achieves a ratio of 11/9 · OPT + 6/9 (uses at most 11/9 times optimal bins). Understanding these bounds guides heuristic selection and helps estimate solution quality.

2. Symmetry Breaking in Bin Indexing

Bins are interchangeable; to avoid redundant states, break symmetry by:

• Labeling bins in order of first use
• Enforcing that bins are "packed" (no gaps in bin IDs)
• Using channeling constraints to link bin use to item assignments

3. Greedy Lookahead with Local Backtracking

Instead of pure online, peek at the next k items (e.g., k=5) and solve a small subproblem optimally before committing. This balances responsiveness (small k) with solution quality (larger k).

4. Constraint Propagation: All-Different and Cumulative

Use global constraints like cumulative (borrowed from scheduling) to track bin capacities in bulk, propagating capacity violations early to prune the search space.

---

Challenge Corner

Open Questions for Reflection:

1. Adaptivity: Suppose you observe that future items tend to cluster around sizes 2, 5, and 8 (in a bin of capacity 10). Can you design a dynamic heuristic that exploits this pattern better than standard Worst-Fit?

2. Lookahead budget: Given a computational budget of 1 second per item, how large a lookahead window (k) would you use, and how would you solve the lookahead subproblem (exact vs. heuristic)?

3. Hybrid approach: Could you combine the fast greedy heuristic (First Fit) with occasional constraint-checking phases to "repair" bad assignments? When and how often would you trigger repairs?

4. Stochastic variant: If item sizes are random (e.g., uniform on [1, C/2]), can you compute an a priori bin count that guarantees feasibility with high probability?

---

References

1. Coffman Jr., E. G., Garey, M. R., & Johnson, D. S. (1984). "Approximation algorithms for bin packing: A survey." In Approximation algorithms for NP-hard problems (pp. 46–93). PWN-Polish Scientific Publishers. — Classic reference on worst-case analysis of online bin packing.

2. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. Chapters 1 & 4 cover CSP modeling and global constraints; Chapter 5 addresses scheduling and resource allocation.

3. Vallada, E., Ruiz, R., & Minella, G. (2008). "New best solutions for the flow shop scheduling problem." Journal of the Operational Research Society, 59(12), 1645–1655. — Demonstrates integration of metaheuristics with constraint-based approaches for online scheduling.

4. Bengio, Y., Lodi, A., & Prouvost, A. (2021). "Machine learning for combinatorial optimization: A methodological survey." arXiv preprint arXiv:2012.09577. — Survey of hybrid ML-CP methods, including learning policies for online resource allocation.

---

Next time: Dive into Resource-Constrained Project Scheduling with Temporal Constraints and discover how critical-path methods meet constraint propagation!

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~10 AIC · ⌖ ~7 AIC · ⊞ 7.1K · ◷

• expires on Nov 7, 2026, 3:30 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #73759.