Exact Solution of the Two-Dimensional Finite Bin Packing Problem
Silvano Martello, Daniele Vigo
Management Science · 1998 · Volume 44 · Issue 3
Abstract
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.
Keywords
Cutting and Packing, Branch-and-Bound, Worst-Case Analysis
Enable JavaScript for citation tools and additional paper interactions.