2DPackLIB: 2-Dimensional Packing Problems Library

Page maintained by M. Iori (manuel.iori@unimore.it), V. L. de Lima (vloti@ic.unicamp.br), S. Martello (silvano.martello@unibo.it), F. K. Miyazawa (fkm@ic.unicamp.br), and M. Monaci (michele.monaci@unibo.it).

 

The 2DPackLIB contains benchmarks and links for two-dimensional orthogonal packing problems. 

If you need to refer to material in this library, please cite Iori M., de Lima V.L., Martello S., Miyazawa F.K., Monaci M., Exact solution techniques for two-dimensional cutting and packing, European Journal of Operational Research, 2021 (in press).

Two-dimensional orthogonal packing problems

We consider two-dimensional orthogonal cutting and packing problems where both items and bins are rectangles. The four main problems in this area are:

  • 2D Strip Packing Problem (2D-SPP): find a packing with minimum height;
  • 2D Bin Packing Problem (2D-BPP): pack the items into the minimum number of bins;
  • 2D Knapsack Problem (2D-KP): find a packing of maximum value;
  • 2D Orthogonal Packing Problem (2D-OPP): determine the existence of a feasible packing.

We also consider a number of variants studied in the literature, such as:

  • Orthogonal Rotations;
  • Guillotine Cuts;
  • Variable-sized Bins;
  • Loading/Unloading Constraints.

Some related problems are:

  • Pallet Loading Problem;
  • Continuous Berth Allocation Problem.

Surveys and typologies for two-dimensional orthogonal cutting and packing

H. Dyckhoff. A typology of cutting and packing problemsEuropean Journal of Operational Research, 44(2):145–159, 1990.

A. Lodi, S. Martello, and D. Vigo. Recent advances on two-dimensional bin packing problemsDiscrete Applied Mathematics,, 123(1):379–396, 2002.

A. Lodi, S. Martello, and M. Monaci. Two-dimensional packing problems: A surveyEuropean Journal of Operational Research,, 141(2):241–252, 2002.

G. Wäscher, H. Haußner, and H. Schumann. An improved typology of cutting and packing problemsEuropean Journal of Operational Research, 183(3):1109–1130, 2007.

N. Ntene and J.H. van Vuuren. A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problemDiscrete Optimization,, 6(2):174–188, 2009.

A. Lodi, S. Martello, M. Monaci, and D. Vigo. Two-dimensional bin packing problems. In V. Th. Paschos, Paradigms of Combinatorial Optimization: Problems and New Approaches, pages 107–129, John Wiley & Sons, 2014.

E. Silva, J.F. Oliveira, and G. Wäscher. The pallet loading problem: a review of solution methods and computational experimentsInternational Transactions in Operational Research,, 23(1-2):147–172, 2016.

J.F. Oliveira, A. Neuenfeldt Júnior, E. Silva, and M.A. Carravilla. A survey on heuristics for the two-dimensional rectangular strip packing problemPesquisa Operacional,, 36(2):197–226, 2016.

H. I. Christensen, A. Khan, S. Pokutta, and P. Tetali. Approximation and online algorithms for multidimensional bin packing: A surveyComputer Science Review,, 24:63–79, 2017.

R. Alvarez-Valdes, M.A. Carravilla, and J.F. Oliveira. Cutting and Packing. In R. Martí, P.M. Pardalos, and M.G.C. Resende, Handbook of Heuristics, 931–977, Springer International Publishing, 2018.

M. Russo, M. Boccia, A. Sforza, and C. Sterle. Constrained two-dimensional guillotine cutting problem: upper-bound review and categorizationInternational Transactions in Operational Research,, 27:794834, 2020.

V.M.R. Bezerra, A.A.S. Leao, J.F. Oliveira, and M.O. Santos. Models for the two-dimensional level strip packing problem - a review and a computational evaluationJournal of the Operational Research Society,, 71(4):606627, 2020.

Iori M., de Lima V.L., Martello S., Miyazawa F.K., Monaci M., Exact solution techniques for two-dimensional cutting and packing, European Journal of Operational Research, 2020 (in press).


Benchmarks

We provide benchmark sets that have been used to test two-dimensional cutting and packing methods. For each set of instances, we highlight the main problem for which the set was proposed, and the most recent papers that solved them as other problems. The sets of instances are in 5 groups: a group for each of the four main problems and an additional group for variants.

 

Benchmarks originally proposed for the 2D-SPP

BENG (link)

These are the instances proposed for the 2D-SPP by Bengtsson (1982) and most recently solved by Côté, Dell'Amico and Iori (2014).

They have also been solved as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017).

N and T (link)

These are the instances proposed for the 2D-SPP by Hopper and Turton (2000).

They have also been solved as a 2D-OPP by Côté and Iori (2018).

C / HT (link)

These are the instances proposed for the 2D-SPP by Hopper and Turton (2001) and most recently solved by Côté, Dell'Amico and Iori (2014).

They have also been solved as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017) and as a 2D-OPP by Côté and Iori (2018).

BKW (link)

These are the instances proposed for the 2D-SPP by Burkee, Kendall, and Whitwell (2004) and most recently solved by Côté, Dell'Amico and Iori (2014).

They have also been solved as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017).

ZDF (link)

These are the instances proposed for the 2D-SPP by Leung and Zhang (2011) and by Zhang et al. (2013).

 

Benchmarks originally proposed for the 2D-BPP

CLASS (link)

These are the instances proposed for the 2D-BPP by Berkey and Wang (1987) and by Martello and Vigo (1998), and most recently solved by Pisinger and Sigurd (2007).

They have also been solved as a 2D-SPP by Côté, Dell'Amico and Iori (2014), as a 2D-SPP with guillotine cuts by Mrad (2015), and as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017).

A (link *)

These are the instances proposed for the 2D-CSP with guillotine cuts by Macedo, Alves, and Valério de Carvalho (2010) and most recently solved by Côté and Iori (2018).

They have also been solved as a 2D-SPP with guillotine cuts by Mrad (2015).

 

Benchmarks originally proposed for the 2D-KP

CGCUT / ChW (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Christofides and Whitlock (1977) and most recently solved by Velasco and Uchoa (2019) and Martin et al. (2020).

They have also been solved as a 2D-SPP by Côté, Dell'Amico and Iori (2014) and as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017).

WANG (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Wang (1983) and most recently solved by Velasco and Uchoa (2019).

NGCUT (link)

These are the instances proposed for the 2D-KP by Beasley (1985a).

They have also been solved as a 2D-SPP by Côté, Dell'Amico and Iori (2014) and as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017).

GCUT (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Beasley (1985b) and most recently solved by Martin et al. (2020).

They have also been solved as a 2D-SPP by Côté, Dell'Amico and Iori (2014), as a 2D-SPP with guillotine cuts by Mrad (2015), as a 2D-SPP with orthogonal rotations by Delorme, Iori, and Martello (2017), and as a  2D-CSP with guillotine cuts by Cintra et al (2008).

OF (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Oliveira and Ferreira (1990) and most recently solved by Velasco and Uchoa (2019) and Martin et al. (2020).

OKP (link *)

These are the instances proposed for the 2D-KP by Fekete and Schepers (1997).

They have also been solved as a 2D-KP with guillotine cuts by Furini, Malaguti and Thomopulos (2016).

CU and CW (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Fayard, Hifi, and Zissimopoulos (1998) and most recently solved by Velasco and Uchoa (2019).

LU, LW, and LX (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Hifi (2001) and by Russo, Sforza, and Sterle (2014).

APT (link *)

These are the instances proposed for the 2D-KP with guillotine cuts by Alvarez-Valdés, Parajón, and Tamarit (2002) and most recently solved by Velasco and Uchoa (2019).

They have also been solved as a 2D-SPP with guillotine cuts by Mrad (2015) and as a 2D-CSP with guillotine cuts by Côté and Iori (2018).

NGCUTFS (link)

These are the instances proposed for the 2D-KP by Beasley (2004).

Morabito and Pureza (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Morabito and Pureza (2010) and most recently solved by Velasco and Uchoa (2019).

Velasco and Uchoa (link)

These are the instances proposed for the 2D-KP with guillotine cuts by Velasco and Uchoa (2019).

 

Benchmarks originally proposed for the 2D-OPP

CJCM (link)

These are the instances proposed for the 2D-OPP by Clautiaux, Jouglet, Carlier, and Moukrim (2008) and most recently solved by Côté and Iori (2018).

MSB (link)

These are the instances proposed for the 2D-OPP by Mesyagutov, Scheithauer, and Belov (2012) and most recently solved by Côté and Iori (2018).

 

Benchmarks for other variants and related problems

For the 2D-BPP with variable-sized bins, we refer to the instances solved by Wei et al. (2013) that can be downloaded here.

For the 2D-KP with conflict graphs, we refer to the instances proposed by  de Queiroz et al. (2017) that can be downloaded here.

For the 2D-OPP with unloading constraint, we refer to the instances proposed by Côté, Gendreau, and Potvin (2014) that can be donwloaded here.

For the Pallet Loading Problem, we refer to the instances proposed by Birgin, Lobato, and Morabito (2010) that can be downloaded here, and to the instances solved by Delorme, Iori, and Martello (2017) that can be downloaded here.

For the Rectangle Packing Problem, we refer to the instances solved by Delorme, Iori, and Martello (2017) that can be downloaded here.

For the Continuous Berth Allocation Problem, we refer to the instances presented in Xu and Lee (2018) that can be downloaded here.


TwoBinPack: An interactive visual tool for two-dimensional cutting and packing

An open source visual application to interactively solve rectangular cutting and packing problems can be downloaded here. For a full description of the application, see Costa et al. (2017). Instructions to use the TwoBinGame can be found in video.


Bibliography and useful links

A BibTex file containing all the references from the survey by Iori et al. (2020) can be downloaded here.

Here are some interesting links related to two-dimensional cutting and packing problems:


Updates

If you have any suggestions or if you would like to have the instances solved by your paper included in this page, please contact us by some of the e-mails addresses in the beginning of this page.


References

R. Alvarez-Valdés, A. Parajón, and J. Tamarit (2002). A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers & Operations Research, 29(7):925–947.

J.E. Beasley (1985a) An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33(1):49–64.

J. E. Beasley (1985b). Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society, 36(4):297306.

J.E. Beasley (2004). A population heuristic for constrained two-dimensional non-guillotine cutting. Discrete Optimization, 3(1):601-627.

B.-E. Bengtsson (1982). Packing rectangular pieces - a heuristic approach. The Computer Journal 25(3):353357, 1982.

J.O. Berkey and P. Y. Wang (1987). Two dimensional finite bin packing algorithms. Journal of the Operational Research Society, 38:423–429.

E. G. Birgin, R. D. Lobato and R. Morabito (2010). An effective recursive partitioning approach for the packing of identical rectangles in a rectangleJournal of the Operational Research Society, 61:306–320.

M. Delorme, M. Iori, and S. Martello (2017). Logic Based Benders' Decomposition for Orthogonal Stock Cutting Problem. Computers & Operations Research, 78:290–298.

E.K. Burkee, G. Kendall, and G. Whitwell (2004). A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52(4):655–671.

F. Clautiaux, A. Jouglet, J. Carlier, and A. Moukrim (2008). A new constraint programming approach for the orthogonal packing problem. Computers & Operations Research, 35(3):944–959.

N. Christofides and C. Whitlock (1977). An algorithm for two-dimensional cutting problems. Operations Research 25(1):3044.

G. Cintra, F. Miyazawa, Y. Wakabayashi, and E. Xavier (2008). Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1):61–85.

G. Costa, M. Delorme, M. Iori, E. Malaguti, and S. Martello (2017). A training software for orthogonal packing problems. Computers and Industrial Engineering, 11:139-147.

J.-F. Côté, M. Dell’Amico, and M. Iori (2014). Combinatorial Benders’ cuts for the strip packing problem. Operations Research, 62(3):643–661.

J.-F. Côté, M. Gendreau, and J.-Y. Potvin (2014). An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraintsOperations Research, 62(5):1126–1141.

J.-F. Côté. and M. Iori (2018). The meet-in-the-middle principle for cutting and packing problems. INFORMS Journal on Computing, 30(4):646–661 .

D. Fayard, M. Hifi, and V. Zissimopoulos (1998). An efficient approach for large-scale two-dimensional guillotine cutting stock problems. Journal of the Operational Research Society, 49:1270–1277.

S.P. Fekete and J. Schepers (1997). A new exact algorithm for general orthogonal d-dimensional knapsack problems. In: R. Burkard and G. Woeginger (eds) Algorithms —  ESA 1997. Lecture Notes in Computer Science, 1284. Springer, Berlin, Heidelberg.

F. Furini, E. Malaguti, and D. Thomopulos (2016). Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS Journal on Computing, 28(4):736–751 .

M. Hifi (2001). Exact algorithms for large-scale unconstrained two and three staged cutting problems. Computational Optimization and Applications, 18:63–88.

M. Hifi and C. Roucairol (2001). Approximate and exact algorithms for constrained (un)weighted two-dimensional two-staged cutting stock problems. Journal of Combinatorial Optimization, 5:465–494.

E. Hopper and B.C.H. Turton (2000). Problem generators for rectangular packing problems.

E. Hopper and B.C.H. Turton (2001). An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 128(1):34–57.

M. Iori, V.L. de Lima, S. Martello, F.K. Miyazawa, M. Monaci (2021). Exact solution techniques for two-dimensional cutting and packing, European Journal of Operational Research, in press.

S.C.H. Leung, and D. Zhang (2011). A fast layer-based heuristic for non-guillotine strip packing. Expert Systems with Applications, 38(10): 1303213042.

R. Macedo, C. Alves, and J. Valério de Carvalho (2010). Arc-flow model for the two-dimensional guillotine cutting stock problem. Computers & Operations Research 37(6):991–1001.

S. Martello and D. Vigo (1998). Exact solution of the two-dimensional finite bin packing problem. Management Science, 44(3):388–399.

M. Martin, E. Birgin, R. Lobato, R. Morabito, and P. Munari (2020). Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern. International Transactions in Operational Research, 27(2):767–793.

M. Mesyagutov, G. Scheithauer, and G. Belov (2012). LP bounds in various constraint programming approaches for orthogonal packingComputers & Operations Research, 39(10):2425–2438.

R. Morabito and V. Pureza (2010). A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem. Annals of Operations Research, 179:297–315.

M. Mrad (2015). An arc flow-based optimization approach for the two-stage guillotine strip cutting problem. Journal of the Operational Research Society, 66(11):1850-1859.

J.F. Oliveira and J.S. Ferreira (1990). An improved version of Wang’s algorithm for two-dimensional cutting problems. European Journal of Operational Research, 44:256–266.

F.G. Ortmann, N. Ntene, and J.H. van Vuuren (2010). New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems. European Journal of Operational Research, 203(2):306–315.

D. Pisinger and M. Sigurd (2005). The two-dimensional bin packing problem with variable bin sizes and costsDiscrete Optimization, 2(2):154–167.

M. Russo, A. Sforza, and C. Sterle (2014). An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems. Computers & Operations Research, 50:97–114.

A.S. Velasco and E. Uchoa (2019). Improved state space relaxation for constrained two-dimensional guillotine cutting problemsEuropean Journal of Operational Research, 272(1):106–120.

P.Y. Wang (1983). Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, 31:573–586.

L. Wei, W.-C. Oon, W. Zhu, A. Lim (2013). A goal-driven approach to the 2D bin packing and variable-sized bin packing problems. European Journal of Operational Research, 224(1):110–121.

Z. Xu and C.-Y. Lee (2018). New lower bound and exact method for the continuous berth allocation problemOperations Research, 66(3):778–798.

D. Zhang, L. Wei, S.C.H. Leung, Q. Chen (2013). A binary search heuristic algorithm based on randomized local search for the rectangular strip packing problem. INFORMS Journal on Computing, 25(2):332345