A fully general, exact algorithm for nesting irregular shapes

Donald Jones ()

Journal of Global Optimization, 2014, vol. 59, issue 2, 367-404

Abstract: This paper introduces a fully general, exact algorithm for nesting irregular shapes. Both the shapes and material resource can be arbitrary nonconvex polygons. Moreover, the shapes can have holes and the material can have defective areas. Finally, the shapes can be arranged using both translations and arbitrary rotations (as opposed to a finite set of rotation angles, such as 0 $$^\circ $$ ∘ and 180 $$^\circ $$ ∘ ). The insight that has made all this possible is a novel way to relax the constraint that the shapes not overlap. The key idea is to inscribe a few circles in each irregular shape and then relax the non-overlap constraints for the shapes by replacing them with non-overlap constraints for the inscribed circles. These relaxed problems have the form of quadratic programming problems (QPs) and can be solved to optimality to provide valid lower bounds. Valid upper bounds can be found via local search with strict non-overlap constraints. If the shapes overlap in the solution to the relaxed problem, new circles are inscribed in the shapes to prevent this overlapping configuration from recurring, and the QP is then resolved to obtain improved lower bounds. Convergence to any fixed tolerance is guaranteed in a finite number of iterations. A specialized branch-and-bound algorithm, together with some heuristics, are introduced to find the initial inscribed circles that approximate the shapes. The new approach, called “QP-Nest,” is applied to three problems as proof of concept. The most complicated of these is a problem due to Milenkovic that has four nonconvex polygons with 94, 72, 84, and 74 vertices, respectively. QP-Nest is able prove global optimality when nesting the first two or the first three of these shapes. When all four shapes are considered, QP-Nest finds the best known solution, but cannot prove optimality. Copyright Springer Science+Business Media New York 2014

Keywords: Fabric nesting; Leather nesting; Nonconvex polygon; Irregular shape; Inscribed circle; Inner approximation; Global optimization; Quadratic programming; Cutting and packing; Translation; Rotation; Guaranteed optimality (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-013-0129-z (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:59:y:2014:i:2:p:367-404

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-013-0129-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().