A New Algorithm for Optimal Bin Packing

AAAI 2002

TL;DR

This paper introduces "bin completion," a novel branch-and-bound algorithm for the NP-complete bin packing problem. It significantly outperforms existing optimal algorithms, achieving over a thousand-fold speedup on problems with 60 items and solving problems with 90 items in seconds, by exploring a different search space focused on completing bins rather than assigning items.

What Problem Does This Paper Address?

The bin packing problem is a classic optimization challenge: given a set of items of varying sizes and bins of a fixed capacity, the goal is to pack all items into the minimum possible number of bins. This problem is NP-complete, meaning that finding a guaranteed optimal solution becomes computationally intractable as the problem size grows. While approximation algorithms like First-Fit Decreasing (FFD) and Best-Fit Decreasing (BFD) are fast and provide near-optimal solutions, they don't guarantee optimality. For applications where even a single extra bin is costly, or for understanding the true limits of approximation algorithms, finding optimal solutions is crucial. Existing optimal algorithms, like Martello and Toth's, are complex and can be slow, especially on larger problem instances. This paper aims to develop a more efficient algorithm for finding provably optimal solutions to the bin packing problem.

Methods

The paper introduces a new optimal bin packing algorithm called "bin completion." Unlike traditional approaches that iterate through items and decide which bin to place them in, bin completion takes a different perspective: it iterates through bins and determines the undominated sets of items that can "complete" that bin.

Key methodological aspects include:

  • Branch-and-Bound Search: The algorithm uses a branch-and-bound framework to explore the solution space.
  • Bin Completion Strategy: Instead of assigning items to bins, it focuses on completing partially filled bins by finding feasible sets of remaining items.
  • Dominance Relations: The algorithm heavily leverages dominance relations to prune the search space. These relations identify sets of items that are guaranteed to lead to solutions no better than other sets, allowing them to be discarded.
  • Lower Bound Calculation: A simplified and more intuitive derivation of Martello and Toth's L2 lower bound (estimated wasted space) is presented. A more efficient constant-time lower bound is also used during the branch-and-bound search, which sums completed bin waste and estimates remaining bin waste.
  • Problem Space Exploration: The core novelty lies in exploring the problem space by "completing" bins, which appears to be more efficient than the item-centric approach of previous algorithms.

Datasets

The authors conducted extensive experiments using randomly generated problem instances. They generated ten million instances for each problem size from 5 to 50 elements, and one million instances for larger sizes. To simulate real-world scenarios and avoid "easy" problems, item sizes and bin capacities were chosen uniformly from zero to one million. This approach differs from previous work that used smaller integer ranges or truncated distributions.

Key Insights and Ideas

  • Alternative Search Space: The most significant insight is that by changing the search space from "item assignment" to "bin completion," a dramatic improvement in performance for optimal bin packing can be achieved.
  • Asymptotic Advantage: The bin completion algorithm appears to be asymptotically faster than existing optimal algorithms, suggesting it scales much better with problem size.
  • Dominance is Key: The effective use of dominance relations is crucial for pruning the search space and making the algorithm practical.
  • Simplicity and Efficiency: The bin completion algorithm is described as simpler and easier to implement than Martello and Toth's algorithm, while also being significantly faster.
  • Anytime Algorithm: Like other depth-first branch-and-bound algorithms, bin completion is an "anytime" algorithm, meaning it can be stopped at any point to return the best solution found so far, making it useful for applications with varying time constraints.

Key Results

  • Speedup: The bin completion algorithm achieves over a thousand-fold speedup compared to Martello and Toth's algorithm on problems with 60 elements. On problems with 65 elements, it's over 32,000 times faster.
  • Problem Size Increase: The algorithm can solve problems with 90 elements in an average of 2.5 seconds per problem, a significant increase in solvable problem size compared to previous methods.
  • Performance on Hard Problems: While many instances are solved quickly (often matching the lower bound), the algorithm can handle extremely difficult instances that require billions of node generations.
  • Approximation vs. Optimal: The paper highlights that even for large problem sets, the percentage of instances where FFD and BFD yield optimal solutions decreases with problem size, underscoring the need for exact algorithms.

Limitations and Future Work

  • Dominance Testing Efficiency: The authors note that their current implementation generates feasible completions and then tests for dominance, suggesting that directly generating only undominated completions could further improve performance.
  • Generalizability: While the paper focuses on bin packing, the authors believe the "bin completion" approach, by considering constrained regions of a partial solution, could be applicable to other combinatorial optimization and packing problems (e.g., floor planning, cutting stock, VLSI layout).
  • Hard Problem Instances: Despite the significant improvements, extremely hard problem instances still require substantial computational resources, though the paper demonstrates a much greater capacity to tackle them.

Summary updated

BibTeX
@inproceedings{2002new,
  title = {{A New Algorithm for Optimal Bin Packing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure