The minimum raster set problem and its application to the \(d\)-dimensional orthogonal packing problem. (English) Zbl 1403.90574

Summary: We consider the well-known \(d\)-dimensional orthogonal packing problem (OPP-\(d\)). Using the toolset of conservative scales introduced by S. P. Fekete and J. Schepers [Math. Oper. Res. 29, No. 2, 353–368 (2004; Zbl 1082.90095); Math. Methods Oper. Res. 60, No. 2, 311–329 (2004; Zbl 1076.90049)], we are able to change items’ sizes of the initial instance to obtain an equivalent instance with the same solution. In this paper, we present an efficient algorithm for building equivalent instances with certain properties. We also consider the so-called raster model for OPP-\(d\) introduced by G. Belov et al. [Int. Trans. Oper. Res. 16, No. 6, 745–766 (2009; Zbl 1179.90273); OR Spectrum 35, No. 2, 505–542 (2013; Zbl 1263.90069)]. It is a 0/1 ILP model in which the number of variables and constraints depends on the total number of raster points over all dimensions. Using our algorithm, we construct equivalent instances with a reduced number of raster points. We also present an algorithm to find a lower bound on the minimum possible number of raster points over all equivalent instances. Numerical results are presented.


90C27 Combinatorial optimization
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Beasley, J. E., Bounds for two-dimensional cutting, The Journal of the Operational Research Society, 36, 1, 71-74, (1985) · Zbl 0557.90046
[2] Belov, G.; Kartak, V. M.; Rohling, H.; Scheithauer, G., One-dimensional relaxations and LP bounds for orthogonal packing, ITOR, 16, 6, 745-766, (2009) · Zbl 1179.90273
[3] Belov, G.; Kartak, V. M.; Rohling, H.; Scheithauer, G., Conservative scales in packing problems, OR Spectrum, 35, 2, 505-542, (2013) · Zbl 1263.90069
[4] Berkey, J. O.; Wang, P. Y., Two-dimensional finite bin-packing algorithms, The Journal of the Operational Research Society, 38, 5, 423-429, (1987) · Zbl 0611.90079
[5] Boschetti, M.; Montaletti, L., An exact algorithm for the two-dimensional strip-packing problem, 58, 1774-1791, (2010) · Zbl 1228.90090
[6] Caprara, A.; Monaci, M., Bidimensional packing by bilinear programming, Mathematical Programming, 118, 1, 75-108, (2009) · Zbl 1169.90428
[7] Clautiaux, F.; Jouglet, A.; Carlier, J.; Moukrim, A., A new constraint programming approach for the orthogonal packing problem, Computers and Operations Research, 35, 3, 944-959, (2008) · Zbl 1278.90147
[8] Clautiaux, F.; Moukrim, A.; Carlier, J., New data-dependent dual feasible functions and lower bounds for a two-dimensional bin-packing problem, International Journal of Production Research, 47, 2, 537-560, (2009) · Zbl 1231.90319
[9] Côté, J.; Dell’Amico, M.; Iori, M., Combinatorial benders’ cuts for the strip packing problem, Operations Research, 62, 3, 643-661, (2014) · Zbl 1302.90173
[10] Fekete, S. P.; Schepers, J., A combinatorial characterization of higher-dimensional orthogonal packing, Mathematics of Operations Research, 29, 2, 353-368, (2004) · Zbl 1082.90095
[11] Fekete, S. P.; Schepers, J., A general framework for bounds for higher-dimensional orthogonal packing problems, Mathematical Methods of Operations Research, 60, 2, 311-329, (2004) · Zbl 1076.90049
[12] Herz, J. C., Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 16, 5, 462-469, (1972) · Zbl 0265.90057
[13] Kartak, V. M.; Ripatti, A. V.; Scheithauer, G.; Kurz, S., Minimal proper non-IRUP instances of the one-dimensional cutting stock problem, Discrete Applied Mathematics, 187, 120-129, (2015) · Zbl 1327.90118
[14] Khanafer, A.; Clautiaux, F.; Talbi, E.-G., New lower bounds for bin packing problems with conflicts, European Journal of Operational Research, 206, 2, 281-288, (2010) · Zbl 1188.90214
[15] Lancia, G.; Rinaldi, F.; Serafini, P., A time-indexed LP-based approach for MIN-sum job-shop problems, Annals of Operations Research, 186, 1, 175-198, (2011) · Zbl 1225.90053
[16] Martello, S.; Vigo, D., Exact solution of the two-dimensional finite bin packing problem, Management Science, 44, 3, 388-399, (1998) · Zbl 0989.90114
[17] Mesyagutov, M.; Scheithauer, G.; Belov, G., LP bounds in various constraint programming approaches for orthogonal packing, Computers & Operations Research, 39, 10, 2425-2438, (2012) · Zbl 1251.90331
[18] Pessoa, A.; Uchoa, E.; Poggi, M.; Rodrigues, R., Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Mathematical Programming Computation, 2, 259-290, (2010) · Zbl 1208.90119
[19] Rietz, J.; Scheithauer, G.; Terno, J., Families of non-IRUP instances of the one-dimensional cutting stock problem, Discrete Applied Mathematics, 121, 1, 229-245, (2002) · Zbl 1027.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.