Bin packing

Deep dive

How it works

In: item sizes, bin capacity · Out: bin index per item, bin count · State: none offline; residual per open bin online · Cost: O(n log n)

1. Sort items by size, descending (decreasing is what buys the 11/9 guarantee).
2. For each item, find the lowest-index open bin whose residual is at least the item size (First Fit), or the bin with the smallest residual that still fits (Best Fit); if none fits, open a new bin.
3. Find that bin fast: keep a max segment tree over bin residuals and descend left-first to the first leaf with residual >= size. For Best Fit keep a sorted set of (residual, bin) and take the first entry >= size.
4. Compute L1 = ceil(sum / cap). If bins == L1, the packing is optimal. Else the gap is at most 11/9 OPT + 6/9 by theory, usually 0-1 bins in practice.

Code

use std::collections::BTreeSet;

/// Max segment tree over bin residuals: find the leftmost bin that fits in O(log n).
pub struct FirstFit {
    n: usize,        // number of leaves, power of two
    t: Vec<u64>,     // t[1] = root; leaf i at t[n + i]
    used: usize,     // bins opened so far
}

impl FirstFit {
    pub fn new(max_bins: usize, cap: u64) -> Self {
        let n = max_bins.next_power_of_two();
        let mut t = vec![0; 2 * n];
        for i in 0..max_bins { t[n + i] = cap; }       // padding leaves stay 0
        for i in (1..n).rev() { t[i] = t[2 * i].max(t[2 * i + 1]); }
        FirstFit { n, t, used: 0 }
    }
    /// Place `size` into the lowest-index bin with room; None if no bin fits.
    pub fn place(&mut self, size: u64) -> Option<usize> {
        if self.t[1] < size { return None; }
        let mut i = 1;
        while i < self.n {
            i *= 2;
            if self.t[i] < size { i += 1; }             // left child too small: go right
        }
        self.t[i] -= size;
        let bin = i - self.n;
        self.used = self.used.max(bin + 1);
        while i > 1 { i /= 2; self.t[i] = self.t[2 * i].max(self.t[2 * i + 1]); }
        Some(bin)
    }
    pub fn bins_used(&self) -> usize { self.used }
}

/// First Fit Decreasing. Returns bin index per item (input order) and bin count.
pub fn ffd(sizes: &[u64], cap: u64) -> (Vec<usize>, usize) {
    assert!(sizes.iter().all(|&s| s <= cap));
    let mut order: Vec<usize> = (0..sizes.len()).collect();
    order.sort_unstable_by_key(|&i| std::cmp::Reverse(sizes[i]));
    let mut ff = FirstFit::new(sizes.len().max(1), cap);
    let mut assign = vec![0; sizes.len()];
    for i in order { assign[i] = ff.place(sizes[i]).unwrap(); }
    (assign, ff.bins_used())
}

/// Best Fit Decreasing: smallest residual that still fits; ties to lowest index.
pub fn bfd(sizes: &[u64], cap: u64) -> (Vec<usize>, usize) {
    let mut order: Vec<usize> = (0..sizes.len()).collect();
    order.sort_unstable_by_key(|&i| std::cmp::Reverse(sizes[i]));
    let mut open: BTreeSet<(u64, usize)> = BTreeSet::new(); // (residual, bin)
    let mut assign = vec![0; sizes.len()];
    let mut bins = 0;
    for i in order {
        let s = sizes[i];
        let (res, b) = match open.range((s, 0)..).next().copied() {
            Some(x) => { open.remove(&x); x }
            None => { bins += 1; (cap, bins - 1) }
        };
        assign[i] = b;
        open.insert((res - s, b));
    }
    (assign, bins)
}

/// L1 lower bound: ceil(total / cap).
pub fn l1(sizes: &[u64], cap: u64) -> usize {
    (sizes.iter().sum::<u64>() + cap - 1) as usize / cap as usize
}

Tested against a brute-force optimum on 3,000 random instances (4-12 items, capacity 100): all packings valid, FFD/BFD never above 11/9 OPT + 6/9, worst ratio 1.5, 33 extra bins in total over 3,000 instances for each.

Complexity and constants

• Time: sort O(n log n) + n tree descents of O(log n). Next Fit is O(n) with O(1) extra memory.
• Memory: the tree is 2n slots of 8 bytes (use u32 residuals for 8n bytes); the sort permutation is 8n.
• Measured on an Apple Silicon Mac, 1,000,000 items uniform in 1..1000, capacity 1000, single thread, the code above: FFD 119 ms (500,318 bins against L1 500,229, 0.018 % above) and BFD 180 ms (same count). Order of 100 ns per item, split between sort, a log n descent and cache misses on the tree.
• Quality bounds: Next Fit 2 OPT; First Fit and Best Fit at most 1.7 OPT (tight, floor); FFD and BFD at most 11/9 OPT + 6/9. Asymptotic schemes reach OPT + O(log OPT) (Hoberg and Rothvoss) but are not used in practice.

Efficiency

• The bound is memory latency in the tree descent plus the sort, not arithmetic. Keep tree slots at 4 bytes (u32 residuals: 16 per 64-byte cache line) so the top levels stay in L1/L2.
• Work avoided: items larger than cap/2 can never share a bin, so open them directly; for equal-size items use counting sort (integer sizes, O(n + cap)) instead of a comparison sort.
• Batching: for a stream, collect a window, sort it, pack it; larger windows approach the offline guarantee, and no window gives less than First Fit's 1.7 OPT worst case.
• Cheaper alternative: Next Fit is one pass and O(1) memory (at most 2 OPT) for streaming data where only one bin may be open.
• Real savings come from the result: each bin saved is a disk, node, packet or box not paid for or powered. Spend the extra solver time only when an L1-gap remains.

Implementation notes

• Use integer sizes (bytes, millicores, slots); floating residuals break the residual >= size test through rounding. Scale first.
• Keep original indices; sort an index permutation by Reverse(size) rather than moving items.
• Reserve slack explicitly (headroom, metadata) by reducing the capacity passed in, not by special cases.
• Ties in Best Fit: break by lowest bin index for determinism (the tuple key does it).
• Stable output: sort by (size desc, id asc) so repeated runs assign identically.
• For an optimality proof beyond L1, add: items > cap/2 each need their own bin (L2-type bounds, Martello and Toth); if the heuristic count still exceeds the best bound, call an exact method.

Pitfalls

• Plain First Fit on unsorted input: up to 1.7 OPT. The sort is not optional.
• size > cap items: assert them away, or they spin or panic.
• Treating FFD as optimal: it can be one or a few bins off; check against L1 and report the gap.
• Sizes as f64 with <= comparisons: an item fits at 0.1 + 0.2 <= 0.3 only by luck.
• Using the best-fit set without a stable tiebreak, which makes results differ run to run.

Variants and alternatives

In production

Cloud scheduling: Kubernetes scheduler MostAllocated scoring packs pods onto fewest nodes (docs). Manufacturing: the one-dimensional cutting-stock problem (cut ordered lengths from stock rolls or bars) is the same model (Gilmore and Gomory, Delorme et al.). VM and container consolidation in cloud schedulers (spot capacity allocation); packing training sequences into fixed context windows (sequence packing); memory planning of tensors into arenas (tensor memory planning); filling fixed-size media or backup sets; truck and container loading by weight.

Implementations

Sources

• D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Computing 3(4), 1974. paper
• G. Dosa, The tight bound of First Fit Decreasing bin-packing algorithm is FFD(I) <= 11/9 OPT(I) + 6/9, ESCAPE 2007. paper
• G. Dosa, J. Sgall, First Fit bin packing: a tight analysis, STACS 2013. paper
• N. Karmarkar, R. M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, FOCS 1982. paper
• R. Hoberg, T. Rothvoss, A logarithmic additive integrality gap for bin packing, SODA 2017. paper
• J. M. Valerio de Carvalho, Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research 86, 1999. paper
• F. Brandao, J. P. Pedroso, Bin packing and related problems: general arc-flow formulation with graph compression, Computers and Operations Research 69, 2016. paper · code
• P. C. Gilmore, R. E. Gomory, A linear programming approach to the cutting-stock problem, Operations Research 9(6), 1961. paper
• M. Delorme, M. Iori, S. Martello, Bin packing and cutting stock problems: mathematical models and exact algorithms, EJOR 255(1), 2016. paper