Exact Solution of the Two-Dimensional Finite Bin Packing Problem

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.

• 저널Management Science · 44(3) · 388–399
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.44.3.388
• 저자Silvano Martello, Daniele Vigo