1 Introduction

Cutting and packing is a major field in optimization. Two-dimensional (rectangular) cutting and packing problems model indeed a large number of relevant industrial applications. In the former class of problems a set of rectangular items must be cut from a set of rectangular stock units, whereas in the latter a set of rectangular items must be packed into a set of rectangular containers. It is thus clear that the two problems are strongly related, in the sense that cutting an item from a stock unit is practically equivalent to packing an item into a container. In the following, we use the terms cutting and packing interchangeably and we refer to both stock units and containers as bins. Typical cutting applications derive from industrial productions involving steel, wood or glass, where the aim is to reduce waste material. Typical packing applications include optimal use of spaces in warehouses or in packaging processes. According to specific applications, two-dimensional cutting and packing problems may require to optimize different objective functions, and to satisfy specialized side constraints.

In the following, we deal with the most studied variants of these problems, where the edges of the items must be parallel to those of the bin in which they are packed (orthogonal rectangular cutting and packing). Let \({\mathcal {B}}= (W,H)\) be a rectangular bin of width \(W \in {\mathbb {Z}}_+\) and height \(H \in {\mathbb {Z}}_+\), and \({\mathcal {I}}\) be a set of rectangular items, where each item \(i \in {\mathcal {I}}\) has width \(w_i \in {\mathbb {Z}}_+ \) and height \(h_i \in {\mathbb {Z}}_+\) (with \(w_i \le W\) and \(h_i \le H\)). A packing of \({\mathcal {I}}' \subseteq {\mathcal {I}}\) into \({\mathcal {B}}\) can be described as a function \({\mathcal {F}}: {\mathcal {I}}' \rightarrow {\mathbb {Z}}_+^2\) that maps each item \(i \in {\mathcal {I}}'\) to a pair of coordinates \({\mathcal {F}}(i) = (x_i, y_i)\), such that

$$\begin{aligned}&x_i \in \{0,\ldots ,W-w_i\} \text { and } y_i \in \{0,\ldots ,H-h_i\}\,\, (i \in {\mathcal {I}}'), \end{aligned}$$
(1)
$$\begin{aligned}&[x_i,x_i+w_i) \cap [x_j,x_j+w_j) =\emptyset \text { or } [y_i,y_i+h_i) \cap [y_j,y_j+h_j)\nonumber \\&= \emptyset \,\,(i, j \in {\mathcal {I}}', i \not = j). \end{aligned}$$
(2)

In this representation, the bin is located on a Cartesian plane with its edges parallel to the axes and its bottom-left corner on the origin. The coordinates \({\mathcal {F}}(i) = (x_i, y_i)\) represent the position where the bottom-left corner of each \(i \in {\mathcal {I}}'\) is placed. Constraints (1) impose that each item is entirely inside the bin, while constraints (2) forbid overlapping between pairs of items. Constraints (1) and (2) impose that items have fixed orientation (i.e., cannot be rotated), but they can be adapted to consider the popular variant (discussed in Sect. 2) where items can be rotated by 90 degrees.

Iori et al. [26] recently presented a survey on the main exact solution methods for the most popular two-dimensional orthogonal cutting and packing problems. The huge number of algorithms proposed for these problems has involved, along the years, the adoption of many benchmarks for evaluating their performance. The survey provides a precise classification of the different problem variants. Concerning benchmarks and computational experiments, some issues must be considered:

  • The number of benchmarks in the literature is huge, and even instances proposed in the Seventies are still used to evaluate new methods;

  • There is no clear correspondence between tested variants and adopted benchmarks as, due to similarity among some of the variants, the same benchmarks have been adopted for different variants;

  • Many benchmarks are available in different specific libraries, where they are provided in different formats, not always clearly detailed;

  • Some benchmarks were originally published in personal web pages which no longer exist.

Besides the classification of variants and benchmarks, the authors implemented a standardization of the benchmarks and a unified format for the instances, as well as an analysis of the matching variants-benchmarks. We now collected these results and other useful instruments (visual tools, links to surveys, bibliographies) in a publicly available web page, the 2DPackLib.

Web-based libraries for combinatorial optimization problems have become a popular instrument for researchers wanting to study specific fields and to test their findings on reliable benchmarks. The seminal instruments of this kind, realized 30 years ago, are still very active: the OR-Library, developed in 1990 by Beasley [6] (see http://people.brunel.ac.uk/~mastjjb/jeb/info.html), mostly devoted to a number of combinatorial optimization problems, and the QAPLIB, implemented in 1991 by Burkard et al. [11, 12] for the Quadratic Assignment Problem (see https://coral.ise.lehigh.edu/data-sets/qaplib/). In the following decade, Applegate et al. [3] presented a famous, rich web page (see http://www.math.uwaterloo.ca/tsp/) for the Traveling Salesman Problem. In the last ten years, new libraries have been implemented for Mixed Integer Programming (the MIPLIB by Koch et al. [27], see http://miplib.zib.de/), for Vehicle Routing (the VRPH by Groër et al. [22], see http://sites.google.com/site/vrphlibrary/, and the CVRPLIB by Uchoa et al. [45], see http://vrp.atd-lab.inf.puc-rio.br/), and for Bin Packing (the BPPLIB by Delorme et al. [18], see http://or.dei.unibo.it/library/bpplib).

The purpose of this paper is to present the contents of the 2DPackLib and to provide systematized relationships and links that should hopefully assist researchers in the development and testing of new solution approaches.

The library is available at http://or.dei.unibo.it/library/2dpacklib. In the next sections, we describe its contents, namely:

  • Synthetic classification of problems and variants;

  • Pointers to surveys and typologies;

  • Standardized benchmarks and their matching with problems and variants;

  • Bibliographies and additional tools.

2 Classification

Using the basic definitions provided in Sect. 1, the 2DPackLib classifies the main two-dimensional orthogonal cutting and packing problems as follows:

  • Two-Dimensional Strip Packing Problem (2D-SPP): given a set \({\mathcal {I}}\) of items and a width W, determine the minimum H value such that there exists a packing of \({\mathcal {I}}\) into a bin \({\mathcal {B}}= (W, H)\). In this problem, there is a unique container, called strip, having a fixed width and an infinite height;

  • Two-Dimensional Cutting Stock Problem (2D-CSP): given an unlimited number of identical bins and a set \({\mathcal {I}}\) of items, where each item is associated with a demand \(d_i \in {\mathbb {Z}}_+\) (the minimum number of copies to be packed), determine the minimum number of bins needed to pack all demands. The Two-Dimensional Bin Packing Problem (2D-BPP) is the special case in which \(d_i=1\), for all \(i \in {\mathcal {I}}\);

  • Two-Dimensional Knapsack Problem (2D-KP): given a bin \({\mathcal {B}}\) and a set \({\mathcal {I}}\) of items, where each item \(i \in {\mathcal {I}}\) is associated with a profit \(p_i\), determine a subset \({\mathcal {I}}' \subseteq {\mathcal {I}}\) that can be packed into \({\mathcal {B}}\) and such that \(\sum _{i \in I'} p_i\) is a maximum. In the 2D-KP, each item \(i \in {\mathcal {I}}\) may be associated with a maximum number of copies \(b_i\). This version of the problem is known as the constrained 2D-KP, whereas in the unconstrained version of the problem an unlimited number of copies of each item is available;

  • Two-Dimensional Orthogonal Packing Problem (2D-OPP): given a bin \({\mathcal {B}}\) and a set \({\mathcal {I}}\) of items, determine whether there exists a packing of \({\mathcal {I}}\) into \({\mathcal {B}}\).

Many variants of these problems have been studied in the literature, the most popular ones being:

  • guillotine cuts: in each bin, cuts are restricted to be edge-to-edge and parallel to the edges of the bin. A cut splits a bin into two rectangles, which in turn can be waste, items, or bins to be recursively cut again;

  • orthogonal rotations: items are allowed to be rotated by 90 degrees, as opposed to having fixed orientation;

  • variable-sized bins: this variant arises when, instead of an unlimited number of identical bins, one is given a set of bin types, each having a specific size (width and height), cost, and availability. Typically, this variant is studied for problems 2D-CSP and 2D-BPP;

  • loading and unloading constraints: a packing is associated with a loading/unloading item sequence and must be such that each item can be loaded/unloaded with no need to physically repositioning other items.

These problems are strongly \({\mathcal {N}}{\mathcal {P}}\)-hard (the 2D-OPP, strongly \({\mathcal {N}}{\mathcal {P}}\)-complete) and very difficult to solve in practice. The combinations problem-variant produce a high number of specific issues, and many of them have been investigated in the literature. (The survey [26] examines over 180 related references.)

3 Surveys and typologies

In 1990, Dyckhoff [19] proposed the first typology for classifying cutting and packing problems. Other typologies were later developed by Lodi et al. [31] (further extended by Martello et al. [34]) and Wäscher et al. [48]. Table 1 provides the classification of the optimization problems considered in the 2DPackLib according to the different typologies. The classification by Lodi et al. [31] also covers the variants that consider orthogonal rotations (‘R’ instead of ‘O’ in the second field) and guillotine cuts (‘G’ instead of ‘F’ in the third field).

Table 1 Problem classifications according to classical typologies
Full size table

In the Noughties, surveys on two-dimensional packing problems were presented by Lodi et al. [29, 32], while Ntene and van Vuuren [38] produced a specialized review and comparison of guillotine heuristics for the 2D-SPP.

In the following decade, a survey on general two-dimensional packing problems was proposed by Alvarez-Valdes et al. [1]. Surveys on specific problems, variants, and methodologies were produced by Lodi et al. [30] (2D-BPP and 2D-SPP), Silva et al. [44] (pallet loading problem, a variant of the 2D-BPP in which one has to pack, with orthogonal rotations, the maximum number of identical items into a single bin), Oliveira et al. [40] (2D-SPP), Christensen et al. [14] (approximation and online algorithms), and Russo et al. [41] (upper bounds for problems with guillotine cuts).

Finally, in the last two years, Bezerra et al. [10] proposed a survey on a special case of the 2D-SPP, while Iori et al. [26] reviewed exact algorithms for two-dimensional cutting and packing problems.

The 2DPackLib provides direct pointers to the PDF files of all surveys mentioned above (journal subscriptions may be requested).

4 Benchmarks

This is the most relevant section of the 2DPackLib. Many benchmarks have been proposed to evaluate the computational performances of algorithms for different variants of two-dimensional cutting and packing problems. Unfortunately the literature has a number of drawbacks: unclear correspondence between variants and benchmarks, non-uniform data formats, sometimes hard to understand, unavailability of benchmarks included in dead personal web pages.

In order to facilitate future computational studies, we converted the main benchmark sets to a standard format that comprises the four main 2D cutting and packing problems with identical bins. For that, let W and H be, respectively, the width and height of the bin, and \(w_i\), \(h_i\), \(d_i\), \(b_i\), and \(p_i\) the width, height, demand, maximum number of copies, and profit of each item \(i \in {\mathcal {I}} = \{1,\ldots ,m\}\). The instances are in the following format:

  • m

  • \(W\ H\)

  • For each item \(i\ (i=1,\ldots ,m)\): \(i\ w_i\ h_i\ d_i\ b_i\ p_i\)

The width and height of the items appear in all problems. The demands appear in the 2D-CSP and, sometimes, in variants of the 2D-SPP and the 2D-OPP. The maximum number of copies of items is usually considered in the constrained 2D-KP and variants. The profit is considered in the 2D-KP only.

The format can obviously be used for the variants that include guillotine cuts and orthogonal rotations as well, but not for the cases of loading/unloading constraints and variable-sized bins. However, very few benchmarks have been proposed for these two cases, and a more general format for handling them would be considerably more complex for the most commonly used benchmarks. The library provides however pointers to benchmarks for a number of variants and related problems that do not fall in our format.

The benchmark sets can be downloaded, in the unified format, from the 2DPackLib as Zip files. Since most benchmarks have been adopted for different problem variants, the library also provides, for each benchmark, an up-to-date list of recently published results on different problems. The next sections provide a synthetic description of the benchmark sets.

4.1 Benchmarks originally proposed for the 2D-SPP

  • N and T: two benchmarks, composed by 35 instances each, proposed by Hopper and Turton [25]. The number of items ranges between 17 and 199 and the strip width is always equal to 200;

  • C: 21 instances proposed by Hopper and Turton [24], in which the number of items ranges between 16 and 197, and the width of the strip ranges between 20 and 160. The instances are generated so that the optimal solution is known in advance. A subset of 9 instances from this benchmark has been referred to as "HT" by some authors;

  • BKW: 13 instances proposed by Burke et al. [13], in which the number of items ranges between 10 and 3152, and the width of the strip ranges between 40 and 640. These instances, that are also referred to as "n" by some authors, were generated so that an optimal solution consists of a perfect packing that can be produced by guillotine cuts;

  • ZDF: 16 instances produced by Leung and Zhang [28] by combining other instances from the literature. The number of items ranges between 580 and \(75\,032\), and the width of the strips ranges between 100 and 9000.

The files provided for 2D-SPP instances also report a value for H, which is either the optimal height or \(-1\). The first case only occurs for benchmarks where the optimal solution was already produced by the generation process.

4.2 Benchmarks proposed for the 2D-BPP and 2D-CSP

  • BENG: ten instances introduced by Bengtsson [8] by generating both the size of the items and the dimensions of the bins according to a uniform distribution. The number of items ranges between 20 and 200, whereas the largest bin is (40, 25).

  • CLASS: this benchmark includes 500 instances, divided into 10 classes, and was introduced by Berkey and Wang [9] (classes 1 to 6) and by Martello and Vigo [35] (classes 7 to 10). Each class includes instances of different sizes, namely it has 10 instances for each value of the number of items in {20, 40, 60, 80, 100}. The bins are identical for all instances in each class, and they vary from (10, 10) in class 1 to (300, 300) in class 6;

  • A: 43 instances introduced by Macedo et al. [33] for the 2D-CSP with guillotine cuts. In these instances, that are derived from the furniture industry, the number of items ranges between 13 and 809 and the bins are either (2750, 1220), (2550, 2100), or (2470, 2080).

4.3 Benchmarks proposed for the 2D-KP

  • CGCUT: three small instances generated by Christofides and Whitlock [15]. The dimensions and profits of the items were generated following a uniform distribution. Some authors refer to this set as "ChW";

  • WANG: three small instances obtained by Wang [47] by modifying the bin and the maximum number of copies of one instance from CGCUT, and by considering the profit of each item equal to its area;

  • NGCUT: 12 small instances generated by Beasley [5]. The dimensions and profits of the items were generated following a uniform distribution;

  • GCUT: 13 instances proposed by Beasley [4]. The first 12 instances are associated with each combination of numbers of items in the set \(\{10, 20, 30, 50\}\) and bins in the set \(\{(250,250),\) \((500,500), (1000,1000)\}\). The dimensions of the items were generated following a uniform distribution. The last instance corresponds to a real-world problem with 32 items and bin (3000, 3000). In all instances, profits coincide with item areas;

  • OF: two small instances generated by Oliveira and Ferreira [39], where item dimensions follow a beta distribution and profits coincide with item areas;

  • OKP: five instances generated by Fekete and Schepers [21] in the same manner as the NGCUT set. The number of items ranges between 15 and 33 and the width and height of the bins is 100;

  • CU and CW: 22 instances generated by Fayard et al. [20]. The number of items ranges between 25 and 60 and the largest bin is (992, 970). CU has 11 unweighted instances (i.e., with item profits given by their area), whereas CW has 11 weighted instances, where profits are randomly generated;

  • LU, LW, LX: three groups of 5 large-scale instances each, proposed by Hifi [23] and Russo et al. [42]. The number of items ranges between 100 and 550 and the largest bin is \((45\,237, 35\,983)\);

  • APT: 40 instances proposed by Alvarez-Valdés et al. [2]. The range of number of items and dimensions of the bin follows the policies adopted for CU and CW, but the instances also contain some smaller items to increase their difficulty;

  • NGCUTFS: 630 instances generated by Beasley [7] in the same manner as the OKP set, but with the number of items ranging between 40 and 1000;

  • MP: 450 instances proposed by Morabito and Pureza [37]. The number of items is in \(\{10, 20, 30, 40, 50\}\) and the width and height of the bins is 100. This set is divided into three classes of 150 instances and each class is characterized by different ranges used to create the item dimensions;

  • VU: 80 instances proposed by Velasco and Uchoa [46]. The number of items is 50, and the bins have dimensions ranging between 100 and 400. The items are relatively small compared to the bin, a feature often associated with hard instances.

4.4 Benchmarks proposed for the 2D-OPP

  • CJCM: 42 instances proposed by Clautiaux et al. [16]. The number of items ranges between 10 and 23 and the width and height of the bins is 20;

  • MSB: 1080 instances proposed by Mesyagutov et al. [36], divided into two classes. The first class has 630 instances, each with 20 items and width and height of the bins equal to 1000. The second has 450 instances, each with number of items in \(\{10,15,20,25,30\}\) and width and height of the bins equal to 100.

5 Bibliographies and additional tools

The 2DPackLib includes

  • TwoBinPack, an open source software to interactively solve rectangular cutting and packing problems, developed by Costa et al. [17], an application useful to practitioners and developers thanks to its visual tools;

  • the BibTeX file containing almost 200 references, mostly appeared in the last ten years, from the survey by Iori et al. [26];

  • a list of links related to two-dimensional cutting and packing, such as working groups, library pages, and the instance generator developed by Silva et al. [43].

6 Conclusions

We presented the 2DPackLib, a library dedicated to two-dimensional orthogonal cutting and packing problems that provides pointers to surveys and typologies, benchmarks, an interactive visual tool, a BibTeX file of almost 200 references, and a list of relevant links. The benchmarks (comprising over 3000 instances) are standardized to provide a unified format for all the instances. This addresses previous issues on benchmarks with different formats, not always clearly detailed.

We are confident that the 2DPackLib will facilitate future research in the active area of two-dimensional cutting and packing problems.