×

Symmetry-breaking constraints for packing identical rectangles within polyhedra. (English) Zbl 1267.90117

Summary: Two problems related to packing identical rectangles within a polyhedron are tackled in the present work. Rectangles are allowed to differ only by horizontal or vertical translations and possibly \(90°\) rotations. The first considered problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented.

MSC:

90C27 Combinatorial optimization
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley J.E.: An exact two-dimensional non-guillotine cutting tree-search procedure. Oper. Res. 33, 49–64 (1985) · Zbl 0569.90038 · doi:10.1287/opre.33.1.49
[2] Birgin E.G., Lobato R.D.: Orthogonal packing of identical rectangles within isotropic convex regions. Comput. Ind. Eng. 59, 595–602 (2010) · doi:10.1016/j.cie.2010.07.004
[3] Birgin E.G., Lobato R.D., Morabito R.: An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. J. Oper. Res. Soc. 61, 306–320 (2010) · Zbl 1196.90020 · doi:10.1057/jors.2008.141
[4] Birgin, E.G., Lobato, R.D., Morabito, R.: Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J. Oper. Res. Soc. doi: 10.1057/jors.2011.6 · Zbl 1196.90020
[5] Birgin E.G., Martínez J.M., Mascarenhas W.F., Ronconi D.P.: Method of sentinels for packing items within arbitrary convex regions. J. Oper. Res. Soc. 57, 735–746 (2006) · Zbl 1121.90106 · doi:10.1057/palgrave.jors.2602067
[6] Birgin E.G., Morabito R., Nishihara F.H.: A note on an L-approach for solving the manufacturer’s pallet loading problem. J. Oper. Res. Soc. 56, 1448–1451 (2005) · Zbl 1142.90469 · doi:10.1057/palgrave.jors.2601960
[7] Birgin E.G., Martínez J.M., Nishihara F.H., Ronconi D.P.: Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization. Comput. Oper. Res. 33, 3535–3548 (2006) · Zbl 1110.90072 · doi:10.1016/j.cor.2005.03.031
[8] Cao F., Du D.-Z., Gao B., Wan P.-J., Pardalos P.M.: Minimax problems in combinatorial optimization. In: Du, D.-Z., Pardalos, P.M. (eds) Minimax and Applications, pp. 262–285. Kluwer Academic Publishers, Dordrecht (1995) · Zbl 0847.90113
[9] Cassioli A., Locatelli M.: A heuristic approach for packing identical rectangles in convex regions. Comput. Oper. Res. 38, 1342–1350 (2011) · Zbl 1208.90141 · doi:10.1016/j.cor.2010.12.001
[10] Floudas, C.A., Pardalos, P.M. (eds): Encyclopedia of Optimization, , 2nd edn. Springer, Berlin (2009) · Zbl 1156.90001
[11] Hurkens, C.A.J., Lodi, A., Martello, S., Monaci, M., Woeginger, G.J.: Complexity and approximation of an area packing problem. Optim. Lett. doi: 10.1007/s11590-010-0246-2 (in press) · Zbl 1257.90083
[12] Kallrath J.: Cutting circles and polygons from area-minimizing rectangles. J. Global Optim. 43, 299–328 (2009) · Zbl 1169.90434 · doi:10.1007/s10898-007-9274-6
[13] Lodi A., Monaci M.: Integer linear programming models for 2-staged two-dimensional Knapsack problems. Math. Program. 94, 257–278 (2003) · Zbl 1030.90064 · doi:10.1007/s10107-002-0319-9
[14] Mascarenhas W.F., Birgin E.G.: Using sentinels to detect intersections of convex and nonconvex polygons. Comput. Appl. Math. 29, 247–267 (2010) · Zbl 1201.90202
[15] Ostrowski J., Linderoth J., Rossi F., Smirglio S.: Solving Steiner triple covering problems. Otima 83, 1–7 (2010)
[16] Sawaya N.W., Grossmann I.E.: A cutting plane method for solving linear generalized disjunctive programming problems. Comput. Chem. Eng. 29, 1891–1913 (2005) · doi:10.1016/j.compchemeng.2005.04.004
[17] Xie W., Sahinidis N.V.: A branch-and-bound algorithm for the continuous facility layout problem. Comput. Chem. Eng. 32, 1016–1028 (2008) · doi:10.1016/j.compchemeng.2007.05.003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.