Packing Problems

Manufacturer's pallet loading problem

  • This problem consists on arranging (orthogonally and without overlapping) the maximum number of identical rectangles into a large rectangle.

    (146,84,18,5) (146,84,11,8) (2530,1320,137,95)

    E. G. Birgin, R. D. Lobato and R. Morabito, "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle", Journal of the Operational Research Society 61, pp. 306-320, 2010. [Abstract] [pdf] [ps] [code and additional information at Lobato's webpage]

    E. G. Birgin, R. Morabito and F. H. Nishihara "A note on an L-approach for solving the manufacturer's pallet loading problem", Journal of the Operational Research Society 56, pp. 1448-1451, 2005. [Abstract] [pdf] [ps]

    R. Andrade and E. G. Birgin, "Symmetry-breaking constraints for packing identical orthogonal rectangles within polyhedra", Optimization Letters 7, pp. 375-405, 2013. [Abstract] [pdf]

Distributor's pallet loading problem

  • This problem consists of cutting different types of rectangular pieces from a rectangular plate.

    E. G. Birgin, R. D. Lobato and R. Morabito, "Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm", submitted, 2010. [Abstract] [pdf] [additional information at Lobato's webpage]

  • MIP models considering leftovers:

    R. Andrade, E. G. Birgin, and R. Morabito, "Two-stage two-dimensional guillotine cutting stock problems with usable leftovers", International Transactions in Operational Research, to appear (DOI: 10.1111/itor.12077). [Abstract] [pdf]

    R. Andrade, E. G. Birgin, R. Morabito, and D. P. Ronconi, "MIP models for two-dimensional non-guillotine cutting problems with usable leftovers", Journal of the Operational Research Society, to appear (DOI: 10.1057/jors.2013.108). [Abstract] [pdf]

Packing circles and spheres by Nonlinear Optimization

We considered several packing problems using nonlinear programming models:

  • Minimizing the object dimensions in circle and sphere packing problems:

    E. G. Birgin and F. N. C. Sobral, "Minimizing the object dimensions in circle and sphere packing problems", Computers & Operations Research 35, pp. 2357-2375, 2008. [Abstract] [pdf] [ps] [Website and code]

    E. G. Birgin and J. M. Gentil, "New and improved results for packing identical unitary radius circles within triangles, rectangles and strips", Computers & Operations Research 37, pp. 1318-1327, 2010. [Abstract] [pdf] [Website and code]

  • Packing the maximum number of identical circles within circular and rectangular regions:

    E. G. Birgin, J. M. Martínez and D. P. Ronconi, "Optimizing the Packing of Cylinders into a Rectangular Container: A Nonlinear Approach", European Journal of Operational Research 160, pp. 19-33, 2005. [Abstract] [pdf] [ps] [Code]

  • Packing the maximum number of identical circles within ellipses:

    E. G. Birgin, L. H. Bustamante, H. F. Callisaya, and J. M. Martínez, "Packing circles within ellipses", International Transactions in Operational Research 20, pp. 365-389, 2013. [Abstract] [pdf] [Code]

Packing rectangles within arbitrary convex regions by Nonlinear Optimization

We considered several packing problems using nonlinear programming models:

  • Packing of the maximum number of rectangular items within arbitrary convex regions:

    E. G. Birgin and R. D. Lobato, "Orthogonal packing of identical rectangles within isotropic convex regions", Computers & Industrial Engineering 59, pp. 595-602, 2010. [Abstract] [pdf] [Code] [additional information at Lobato's webpage]

    E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi, "Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization", Computers & Operations Research 33, pp. 3535-3548, 2006. [Abstract] [pdf] [ps] [Code]

  • Packing of the maximum number of free-rotated rectangular (and arbitrary polygonal) items within arbitrary convex regions:

    E. G.Birgin, J. M. Martínez, W. F. Mascarenhas and D. P. Ronconi "Method of Sentinels for Packing Items whitin Arbitrary Convex Regions", Journal of the Operational Research Society 57, pp. 735-746, 2006. [Abstract] [pdf] [ps].

    W. F. Mascarenhas and E. G. Birgin, "Using sentinels to detect intersections of convex and nonconvex polygons", Computational & Applied Mathematics 29, pp. 247-267, 2010. [Abstract] [pdf] [ps]

Valid XHTML 1.0 Strict

Valid CSS!