Recursive partitioning approach
for the Distributor's Pallet Loading Problem

Problem instances

Here are available some instances found in the literature for the unconstrained two-dimensional cutting problem of rectangular pieces. The instances presented in the files have the following format: the first line contains the number m of piece types, the second line contains the length L and the width W of the large rectangle, and the i-th line of the next m lines contains the length l_i, the width w_i and the value v_i of the i-th piece.

m
L W
l1 w1 v1
l2 w2 v2
   .
   .
   .
lm wm vm

In some instances, the values of the pieces are equal to their respective areas, that is, v_i = l_iw_i for i = 1, …, m. In this case, the values of the pieces are omitted in some files, which have the following format.

m
L W
l1 w1
l2 w2
  .
  .
  .
lm wm

Below are the instances and the references to the articles where these instances have been found. Some of these instances can also be found at OR-Library and www.laria.u-picardie.fr/hifi/OR-Benchmark/.

• G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi and E. C. Xavier. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, Volume 191, Issue 1, Pages 61-85, 2008.
  doi:10.1016/j.ejor.2007.08.007

  Instance	L	W	m
  GCUT14	3500	3500	42
  GCUT15	3500	3500	52
  GCUT16	3500	3500	62
  GCUT17	3500	3500	82

• Y. Cui, Z. Wang, J. Li. Exact and heuristic algorithms for staged cutting problems. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, Volume 219, Issue 2, Pages 201-207, 2005.
  doi:10.1243/95440505X8136

  Instance	L	W	m
  B1	4000	2000	30
  B2	4000	2000	30
  B3	4000	2000	30
  B4	4000	2000	30
  B5	4000	2000	30
  B6	4000	2000	30
  B7	4000	2000	180

• Ramón Alvarez-Valdés, Antonio Parajón and José Manuel Tamarit. A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers & Operations Research, Volume 29, Issue 7, Pages 925-947, 2002.
  doi: 10.1016/S0305-0548(00)00095-2

  Instance	L	W	m
  APT10	2097	1713	51
  APT11	2600	1612	58
  APT12	2662	1941	35
  APT13	1674	2090	54
  APT14	2090	2138	42
  APT15	2222	2726	49
  APT16	2899	2614	53
  APT17	2313	1962	59
  APT18	2775	2105	31
  APT19	2284	2994	35
  APT20	2840	2858	45
  APT21	2866	1784	48
  APT22	2711	2110	52
  APT23	1856	2636	53
  APT24	2070	2729	44
  APT25	2885	1715	36
  APT26	2359	1656	48
  APT27	1793	1875	48
  APT28	2020	2796	54
  APT29	1839	2829	59

• M. Hifi. Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems. Computational Optimization and Applications, Volume 18, Issue 1, Pages 63-88, 2001.
  doi:10.1023/A:1008743711658

  Instance	L	W	m
  LU1	20789	23681	100
  LU2	25587	34563	100
  LU3	37587	27563	150
  LU4	45237	35983	200
  U4	7350	6579	40
  W4	7500	7381	80
  LW1	20789	23681	100
  LW2	25587	34563	100
  LW3	37587	27563	150
  LW4	45237	35983	200
  MW1	100	156	10
  MW2	253	294	10
  MW3	318	473	10
  MW4	501	556	10
  MW5	750	806	10

• D. Fayard, M. Hifi and V. Zissimopoulos. An Efficient Approach for Large-Scale Two-Dimensional Guillotine Cutting Stock Problems. Journal of the Operational Research Society, Volume 49, Issue 12, Pages 1270-1277, 1998.
  doi:10.2307/3010152

  Instance	L	W	m
  UU1	500	500	25
  UU2	750	800	30
  UU3	1100	1000	25
  UU4	1000	1200	38
  UU5	1450	1300	50
  UU6	2050	1457	38
  UU7	1465	2024	50
  UU8	2000	2000	55
  UU9	2500	2460	60
  UU10	3500	3450	55
  UU11	3500	3765	25
  UW1	500	500	25
  UW2	560	750	35
  UW3	700	650	35
  UW4	1245	1015	45
  UW5	1100	1450	35
  UW6	1750	1542	47
  UW7	2250	1875	50
  UW8	2645	2763	55
  UW9	3000	3250	45
  UW10	3500	3650	60
  UW11	555	632	30

• M. Hifi. The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems. European Journal of Operational Research, Volume 97, Issue 1, Pages 41-52, 1997.
  doi:10.1016/S0377-2217(96)00060-4

  Instance	L	W	m
  U1	4500	5000	10
  U2	5050	4070	10
  U3	7350	6579	20
  W1	5000	5000	20
  W2	3427	2769	20
  W3	7500	7381	40

• M. Hifi and V. Zissimopoulos. A recursive exact algorithm for weighted two-dimensional cutting. European Journal of Operational Research, Volume 91, Issue 3, Pages 553-564, 1996.
  doi:10.1016/0377-2217(95)00343-6

  Instance	L	W	m
  HZ2	99	80	5

• M. Hifi and V. Zissimopoulos. Une amélioration de l'algorithme récursif de Herz pour le problème de découpe à deux dimensions. RAIRO, Recherche Opérationnelle, Volume 30, Issue 2, Pages 111-125, 1996.

  Instance	L	W	m
  HZ1	78	67	6

• R. N. Morabito, M. N. Arenales and V. F. Arcaro. An and-or-graph approach for two-dimensional cutting problems. European Journal of Operational Research, Volume 58, Issue 2, Pages 263-271, 1992.
  doi:10.1016/0377-2217(92)90212-R

  Instance	L	W	m
  M1	100	156	10
  M2	253	294	10
  M3	318	473	10
  M4	501	556	10
  M5	750	806	10

• J. E. Beasley. Algorithms for Unconstrained Two-Dimensional Guillotine Cutting. The Journal of the Operational Research Society, Volume 36, Issue 4, Pages 297-306, 1985.
  doi:10.2307/2582416

  Instance	L	W	m
  GCUT1	250	250	10
  GCUT2	250	250	20
  GCUT3	250	250	30
  GCUT4	250	250	50
  GCUT5	500	500	10
  GCUT6	500	500	20
  GCUT7	500	500	30
  GCUT8	500	500	50
  GCUT9	1000	1000	10
  GCUT10	1000	1000	20
  GCUT11	1000	1000	30
  GCUT12	1000	1000	50
  GCUT13	3000	3000	32

• J. C. Herz. Recursive Computational Procedure for Two-dimensional Stock Cutting. IBM Journal of Research and Development, Volume 16, Issue 5, Pages 462-469, 1972.

  Instance	L	W	m
  H	127	98	5