Exact Solution of the Two-Dimensional Finite Bin Packing Problem

Silvano Martello and Daniele Vigo
Additional contact information
Silvano Martello: Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Bologna, Italy
Daniele Vigo: Dipartimento di Elettronica, Informatica e Sistemistica, University of Bologna, Bologna, Italy

Management Science, 1998, vol. 44, issue 3, 388-399

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 (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (80)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.3.388 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:3:p:388-399

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().