---

title: "Bin Packing Problem" description: "Start with the classic bin packing problem, learning how to use OR-Tools CP-SAT solver to optimally pack items into bins." order: 1

Bin Packing Problem

The bin packing problem is one of the most classic combinatorial optimization problems. Imagine you run a moving company with boxes of various sizes that need to be loaded into trucks. How do you use the fewest trucks to pack everything?

That is the Bin Packing problem.

Installing OR-Tools

pip install ortools

Solving Bin Packing with CP-SAT

from ortools.sat.python import cp_model

# Items (volume of each item)
items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
bin_capacity = 100

num_items = len(items)
num_bins = num_items  # at most as many bins as items

model = cp_model.CpModel()

# Variables: x[i][b] = 1 if item i is placed in bin b
x = [[model.NewBoolVar(f'x_{i}_{b}') for b in range(num_bins)]
     for i in range(num_items)]

# Variables: used[b] = 1 if bin b is used
used = [model.NewBoolVar(f'used_{b}') for b in range(num_bins)]

# Constraint 1: each item must be placed in exactly one bin
for i in range(num_items):
    model.Add(sum(x[i][b] for b in range(num_bins)) == 1)

# Constraint 2: each bin total volume cannot exceed capacity
for b in range(num_bins):
    model.Add(sum(items[i] * x[i][b] for i in range(num_items)) <= bin_capacity)

# Constraint 3: if bin b is used, at least one item must be in it
for b in range(num_bins):
    model.Add(sum(x[i][b] for i in range(num_items)) >= used[b])
    model.Add(sum(x[i][b] for i in range(num_items)) <= num_items * used[b])

# Objective: minimize number of bins used
model.Minimize(sum(used))

# Solve
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"
=== Bin Packing Results ===")
    print(f"Bins used: {int(solver.ObjectiveValue())}")

    for b in range(num_bins):
        if solver.Value(used[b]):
            bin_items = [i for i in range(num_items) if solver.Value(x[i][b])]
            bin_volume = sum(items[i] for i in bin_items)
            print(f"
Bin {b}: total volume {bin_volume}/{bin_capacity}")
            print(f"  Items: {bin_items}")
            print(f"  Volumes: {[items[i] for i in bin_items]}")
else:
    print("No feasible solution found")

Greedy Algorithms (Large-Scale Problems)

When items exceed 100, CP-SAT becomes very slow. Use greedy heuristic algorithms:

First-Fit Decreasing (FFD)

def first_fit_decreasing(items, capacity):
    """Sort items descending, place each into the first bin that fits"""
    bins = []
    for item in sorted(items, reverse=True):
        placed = False
        for i, remaining in enumerate(bins):
            if remaining >= item:
                bins[i] -= item
                placed = True
                break
        if not placed:
            bins.append(capacity - item)
    return len(bins)

items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
print(f"FFD bins: {first_fit_decreasing(items, 100)}")

Best-Fit Decreasing (BFD)

def best_fit_decreasing(items, capacity):
    """Sort descending, place each into the bin with smallest remaining space"""
    bins = []
    for item in sorted(items, reverse=True):
        best_idx = -1
        best_remaining = capacity + 1
        for i, remaining in enumerate(bins):
            if remaining >= item and remaining - item < best_remaining:
                best_idx = i
                best_remaining = remaining - item
        if best_idx >= 0:
            bins[best_idx] -= item
        else:
            bins.append(capacity - item)
    return len(bins)

print(f"BFD bins: {best_fit_decreasing(items, 100)}")

Algorithm Comparison

| Algorithm | Bins (this example) | Time | Approximation Ratio | |-----------|--------------------|------|-------------------| | CP-SAT (optimal) | 4 | ~1s | 100% | | First-Fit Decreasing | 4 | ~1ms | <= 11/9 x OPT | | Best-Fit Decreasing | 4 | ~1ms | <= 11/9 x OPT | | Next-Fit | 6 | ~0.1ms | <= 2 x OPT |

Time Complexity

| Algorithm | Time | |-----------|------| | CP-SAT (optimal) | Exponential (NP-hard), fast for <50 items | | First-Fit Decreasing | O(n log n + n x bins) | | Best-Fit Decreasing | O(n log n + n x bins) | | Next-Fit | O(n) |

Summary

• Bin Packing = pack all items with minimum bins
• NP-hard - cannot solve large instances in polynomial time
• CP-SAT suitable for small to medium (<50 items) seeking optimal
• FFD/BFD provide near-optimal solutions (11/9 ~ 1.22x approximation)
• Applications: cloud VM placement, logistics loading, warehouse management, memory allocation

---

Bin Packing Is Not Just About Moving

Bin Packing appears everywhere in software engineering:

• Cloud Server Resource Allocation: Packing containers of different sizes into limited physical hosts
• Ad Placement: Fitting maximum ads into limited ad slots
• Video Compression: Packing data blocks of various sizes into fixed-size frames
• Memory Management: OS allocating programs to memory pages
• Database Storage: Distributing records to fixed-size data pages

Next Chapter: From Packing to Scheduling

Bin Packing is about "how to fit things into bins." The next chapter Job Scheduling is about "how to arrange tasks on a timeline" - closer to the scheduling problems you encounter in daily work.

Implementation with OR-Tools (CP-SAT)

from ortools.sat.python import cp_model

def bin_packing_cp(item_weights, bin_capacity):
    """Solve bin packing with CP-SAT for optimal solution."""
    n = len(item_weights)
    # Upper bound: number of bins needed (worst case = each item in its own bin)
    max_bins = n

    model = cp_model.CpModel()

    # Variables
    x = {}
    for i in range(n):
        for b in range(max_bins):
            x[(i, b)] = model.NewBoolVar(f"x_{i}_{b}")

    y = [model.NewBoolVar(f"y_{b}") for b in range(max_bins)]

    # Each item must be assigned to exactly one bin
    for i in range(n):
        model.Add(sum(x[(i, b)] for b in range(max_bins)) == 1)

    # Bin capacity constraint
    for b in range(max_bins):
        model.Add(
            sum(item_weights[i] * x[(i, b)] for i in range(n))
            <= bin_capacity * y[b]
        )

    # Objective: minimize number of bins used
    model.Minimize(sum(y[b] for b in range(max_bins)))

    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        bins_used = sum(solver.Value(y[b]) for b in range(max_bins))
        print(f"Optimal bins needed: {bins_used}")

        for b in range(max_bins):
            if solver.Value(y[b]):
                items = [i for i in range(n) if solver.Value(x[(i, b)])]
                if items:
                    total = sum(item_weights[i] for i in items)
                    print(f"Bin {b}: items {items}, total weight {total}")

        return bins_used
    else:
        print("No optimal solution found")
        return None

# Example
weights = [4, 8, 1, 4, 7, 3, 5, 2, 6, 2]
capacity = 10
result = bin_packing_cp(weights, capacity)

First-Fit Decreasing (FFD) Algorithm

def first_fit_decreasing(item_weights, bin_capacity):
    """
    FFD: Sort items descending, then place each in the first bin that fits.
    Approximation ratio: 11/9 OPT + 6/9 (~1.22x optimal).
    """
    sorted_weights = sorted(item_weights, reverse=True)
    bins = []

    for w in sorted_weights:
        placed = False
        for i in range(len(bins)):
            if bins[i] + w <= bin_capacity:
                bins[i] += w
                placed = True
                break
        if not placed:
            bins.append(w)

    return bins

# Example
weights = [4, 8, 1, 4, 7, 3, 5, 2, 6, 2]
capacity = 10
result = first_fit_decreasing(weights, capacity)
print(f"FFD bins: {len(result)}")
print(f"Bin loads: {result}")

Comparison of Algorithms

| Algorithm | Optimal? | Time Complexity | Approximation Ratio | Best For | |-----------|----------|----------------|-------------------|----------| | CP-SAT | ✅ Yes | Exponential (worst case) | 1.0 (optimal) | Small instances (< 50 items) | | First-Fit Decreasing | ❌ No | O(n log n) | ~1.22x | Large instances, fast solution | | Best-Fit Decreasing | ❌ No | O(n log n) | ~1.22x | Similar to FFD, slightly better avg | | Next-Fit | ❌ No | O(n) | 2.0x | Streaming, online scenarios |

When to Use Each

| Scenario | Recommended Algorithm | |----------|---------------------| | Small set, must be optimal | CP-SAT (OR-Tools) | | Large set, fast solution needed | First-Fit Decreasing | | Real-time streaming (unknown items) | Next-Fit | | Cloud VM placement (many items) | FFD with precomputed sorting |

Summary

Bin packing is a fundamental combinatorial optimization problem with applications in cloud computing, logistics, and resource allocation. Use CP-SAT for optimal solutions on small instances, and FFD for fast near-optimal solutions on large instances.

Key takeaways:

• Bin packing = minimize bins needed to pack all items
• NP-hard — no polynomial-time optimal algorithm exists
• CP-SAT: optimal for small instances (< 50 items)
• FFD: O(n log n), ~1.22x approximation guarantee
• Applications: cloud VM placement, truck loading, warehouse storage
• Real-time streaming: use simple heuristics (Next-Fit)
• Always consider the tradeoff between optimality and computation time

What's Next: Job Scheduling

The next chapter covers job scheduling — assigning tasks to machines to minimize completion time or meet deadlines.