(75c) Globally Optimal Nesting of Irregular Shapes Into a Limited Resource

Cutting irregularly shaped parts from expensive material resources is a problem common to the automotive, garment, and leather industries. For example, flat pieces of steel called blanks are punched from steel coils and later pressed into car parts. Nesting irregular objects into an expensive resource to minimize scrap material is a mixed integer nonconvex optimization problem that features:

? Nonoverlap constraints for irregular parts

? Translational and sometimes rotational freedom of the parts

? Combinatorial possible orderings of the parts within the resource.

The combinatorial complexity inherent in ordering variably-sized parts has been addressed in the context of rectangular strip-packing [7] and the nonconvex constraints associated with packing circles and regular polygons have been integrated into global optimization algorithms [1, 2, 4, 6], but industrially-relevant problems nesting complex, nonconvex shapes are typically solved heuristically [3].

We present a global optimization method to address the nesting of general shapes using a circle relaxation technique that approximates irregular parts with inscribed circles. The circle relaxation of the irregular parts simplifies the constraints, transforming the nesting problem into a mixed-integer quadratically-constrained quadratic program. The global optimum of the circle relaxation provides a valid lower bound to the nesting problem, so we construct an iterative algorithm that optimizes the nesting problem by solving a series of circle relaxation problems. We use our recent computational results in piecewise-linear relaxations of the constraints to underestimate the circle relaxation problem [5]. Finally, we conclude by presenting our computational results on a test suite of industrially-relevant problems.

[1] E. G. Birgin and J. M. Gentil. New and improved results for packing identical unitary radius circles within triangles, rectangles and strips. Comp. Oper. Res., 37(7):1318 ? 1327, 2010.

[2] E. G. Birgin and F. N. C. Sobral. Minimizing the object dimensions in circle and sphere packing problems. Comp. Oper. Res., 35(7):2357 ? 2375, 2008.

[3] M. T. Costa, A. M. Gomes, and J. F. Oliveira. Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet. European J. Oper. Res., 192(1):29 ? 40, 2009.

[4] J. Kallrath. Cutting circles and polygons from area-minimizing rectangles. J. Global Optim., 43(2-3):299 ? 328, 2009.

[5] R. Misener, C. E. Gounaris, and C. A. Floudas. Global optimization of gas lifting operations: A comparative study of piecewise linear formulations. Ind. Eng. Chem. Res., 48(13):6098 ? 6104, 2009.

[6] S. Rebennack, J. Kallrath, and P. M. Pardalos. Column enumeration based decomposition techniques for a class of non-convex MINLP problems. J. Glob. Optim., 43(2 - 3):277 ? 297, 2009.

[7] N. W. Sawaya and I. E. Grossmann. A cutting plane method for solving linear generalized disjunctive programming problems. Comput. Chem. Eng., 29(9):1891 ? 1913, 2005.