zbMATH — the first resource for mathematics

Exact solution of the two-dimensional finite bin packing problem. (English) Zbl 0989.90114
Summary: Given a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the two-dimensional finite bin packing problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI