Two-dimensional Bin Packing Problems

In the two-dimensional bin packing problem (2BP) we are given a set of rectangular items, each characterized by a width and a height, and an unlimited number of finite identical rectangular bins, of given width and height. The problem is to allocate, without overlapping, all the items to the minimum number of bins, with their edges parallel to those of the bins. An important variant of 2BP, which is also used in some approximation algorithms for its solution, is the strip packing problem (2SP), in which the items have to be packed in a strip of given width and infinite height, so as to minimize the height at which the strip is used. Two dimensional packing problems have many industrial applications, especially in cutting (e.g. wood, glass and paper industries) and packing (e.g. transportation, telecommunications and warehousing). We survey recent advances obtained for the two-dimensional bin packing problem.