Bin Completion Algorithms for Multicontainer Packing, Knapsack, and
  Covering Problems
  Many combinatorial optimization problems such as the bin packing and multiple
knapsack problems involve assigning a set of discrete objects to multiple
containers. These problems can be used to model task and resource allocation
problems in multi-agent systems and distributed systms, and can also be found
as subproblems of scheduling problems. We propose bin completion, a
branch-and-bound strategy for one-dimensional, multicontainer packing problems.
Bin completion combines a bin-oriented search space with a powerful dominance
criterion that enables us to prune much of the space. The performance of the
basic bin completion framework can be enhanced by using a number of extensions,
including nogood-based pruning techniques that allow further exploitation of
the dominance criterion. Bin completion is applied to four problems: multiple
knapsack, bin covering, min-cost covering, and bin packing. We show that our
bin completion algorithms yield new, state-of-the-art results for the multiple
knapsack, bin covering, and min-cost covering problems, outperforming previous
algorithms by several orders of magnitude with respect to runtime on some
classes of hard, random problem instances. For the bin packing problem, we
demonstrate significant improvements compared to most previous results, but
show that bin completion is not competitive with current state-of-the-art
cutting-stock based approaches.
