  The Two-dimensional Bin Packing Problem calls for packing a set of
rectangular items into a minimal set of larger rectangular bins. Items must be
packed with their edges parallel to the borders of the bins, cannot be rotated
and cannot overlap among them. The problem is of interest because it models
many real-world applications, including production, warehouse management and
transportation. It is, unfortunately, very difficult, and instances with just
40 items are unsolved to proven optimality, despite many attempts, since the
1990s. In this paper, we solve the problem with a combinatorial Benders
decomposition that is based on a simple model in which the two-dimensional
items and bins are just represented by their areas, and infeasible packings are
imposed by means of exponentially-many no-good cuts. The basic decomposition
scheme is quite naive, but we enrich it with a number of preprocessing
techniques, valid inequalities, lower bounding methods, and enhanced algorithms
to produce the strongest possible cuts. The resulting algorithm behaved very
well on the benchmark sets of instances, improving on average upon previous
algorithms from the literature and solving for the first time a number of open
instances.
