Exact Solution of the Two-Dimensional Finite Bin Packing Problem

TLDR

The Two‑Dimensional Finite Bin Packing Problem seeks the minimum number of standardized stock pieces needed to cut a set of rectangular pieces, is NP‑hard, and has many practical cutting‑and‑packing applications. The study aims to analyze a known lower bound’s worst‑case performance and to propose new lower bounds for use in a branch‑and‑bound algorithm solving the problem exactly. The authors analyze a classic lower bound’s worst‑case performance and develop new lower bounds incorporated into a branch‑and‑bound algorithm for exact solution. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.

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.