An application of Hooke and Jeeves Method as a Constructive Heuristic for the Ellipse Packing Problem

Cássia Cris Beckel, Leonardo Ramos Emmendorfer, Neuza Terezinha Oro


Cutting and packing problems appear in many industrial applications, such as textile, automotive, transportation, etc.. This paper presents a constructive heuristic developed for cutting and packing problems, restricted to the case where a number of non-identical ellipses in an irregular polygon. This problem is related to the gem cut from crude material. The 3D Gems technology proposed in [1] aims to maximize the volumetric use of the gem, taking into account the final market value expected, respecting the industrial standards. The optimization of the ellipses inside the polygon is performed by the Hooke e Jeeves method [2], [3]. Packed ellipses are tangent to the vertexes of a master ellipse, initially positioned at the center of the polygon. Superposition restrictions are imposed and checked at each stage. R2 transformations are applied, which raise parametric ellipse equations. Results illustrate that the proposed heuristic can be applied to polygons with varying shapes, either convex or concave, due to the type of search which is performed in the interior of the polygon. The constructive heuristic was able to find the optimal solutions for the polygons tested.

Full Text:



BRUSSO, Marcos J. et al. Tecnologia 3D Gemas: otimização do aproveitamento de gemas co-radas digitalizadas tridimensionalmente. In: Tecnologias para o setor de Gemas, Joias e Mineração. IGEO/UFRGS, 2010, p. 40-52.

C. C. BECKEL,.Cássia C. Modelagem Computacional e Otimização de secções cônicas em polígonos irregulares de n lados. In: Dissertação (Mestrado em Modelagem Compu-tacional) - Universidade Federal do Rio Grande., 2013.

BAZARAA, M. S. et al. Nonlinear Programming: Theory and Algorithms. New Jer-sey, John Wiley e Sons, 2006.

BECKEL, Cássia C., ORO, Neuza. T. et EMMENDORFER, Leonardo R. An adaptation of the Hooke and Jeeves optimization algorithm for the maximization of the dimensions of an ellipse inscribed in a given non-convex polygon. In: Proceedings of the 5th LNCC Meeting on Computational Modeling. Petrópolis, RJ, 2012.

DRESHAPER., Soft. 3DReshaper. In:https://www., 2015.

CHRISTIANSEN, G. K. Toy Buiding Brick Patent. Oct. 24. Disclaimer filed Mar. 31 - 1978, Interlego A.G. Billund, Denmark, 1961.

MATLAB®, Software MatLab. In:MatLab and Simulink for Technical Computing R2012a, Mathworks Inc., 2002.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.