They have a large number of variables and local minima. In fact, problems with circular objects are very hard optimization problems. However, most NLP solvers fail to identify global optima. Many variants of packing circular objects in the plane have been formulated as nonconvex optimization problems with the hope that these formulations when solved using available nonlinear programming (NLP) solvers yield high quality approximate solutions. The recent trend is to design solution techniques that tackle (to some extent) these two aspects simultaneously. Indeed, the positions of the circular objects are continuous whereas the structure of an optimal pattern has a discrete nature. Obviously, packing circular objects gives rise to optimization problems, but their classification into continuous or discrete problems is fuzzy. Last, there is the issue of computational accuracy and precision. In fact, there exists a continuum of optimal solutions. In addition, one or more of the circular objects may be moved slightly without affecting the optimal solution. An optimal solution may be rotated, reflected or the circular objects reordered hence, the number of equivalent optimal solutions blows up as the number of circular objects increases. With a large number of circular objects to pack, the optimal solution is very difficult to find. Packing circular objects is a challenge to discrete and computational geometry. They include the coverage of a geographical area with cell transmitters, storage of cylindrical drums into containers or stocking them into an open area, packaging bottles or cans into the smallest box, planting trees in a given region as to maximize the forest density and the distance between the trees, and so forth.

These problems have a wide spectrum of applications ranging from natural sciences, to engineering design, to every day life. This paper focuses on problems dealing with circular objects, being two- or three-dimensional. However, the search for exact local extrema is time consuming without any guarantee of a sufficiently good convergence to optimum. One approach to solve this complex problem is to arrange the objects according to some prescribed order in and to search for the exact local extremum. When the geometric objects are objects, the packing problem reduces to a mathematical model whose constraints reflect the conditions of arrangement of objects within the given region, the mutual nonintersection conditions for objects, and any technological constraints that cannot be reduced to purely geometric constraints (as guillotine cuts for rectangular packing). The packing identifies the arrangement and positions of the geometric objects that determine the dimensions of the containing shape and reach the extremum of a specific objective function. Ĭutting and packing problems consist of packing a set of geometric objects/items of fixed dimensions and shape into a region of predetermined shape while accounting for the design and technological considerations of the problem. They are bottleneck problems in computer aided design where design plans are to be generated for industrial plants, electronic modules, nuclear and thermal plants, and so forth. They are encountered in a variety of real-world applications including production and packing for the textile, apparel, naval, automobile, aerospace, and food industries. They are very interesting NP-hard combinatorial optimization problems that is, no procedure is able to exactly solve them in deterministic polynomial time.

IntroductionĬutting and Packing problems are scientifically challenging problems with a wide spectrum of applications. Proofs, to branch-and-bound procedures, to constructive approaches, to multi-start nonconvex minimization, to billiard simulation, to multiphase heuristics, and metaheuristics. They have been tackled using various approaches-based algorithms ranging from computer-aided optimality

These packing problems are NP hard optimization problems with a wide variety of applications. This paper reviews the most relevant literature on efficient models and methods for packing circular objects/items into Euclidean plane regions where the objects/items and regions are either two- or three-dimensional.

Packing problem circles in rectangle