Authors: | Mladenović, Nenad Plastria, Frank Urošević, Dragan |
Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | Reformulation descent applied to circle packing problems | Journal: | Computers and Operations Research | Volume: | 32 | Issue: | 9 | First page: | 2419 | Last page: | 2434 | Issue Date: | 1-Jan-2005 | Rank: | M22 | ISSN: | 0305-0548 | DOI: | 10.1016/j.cor.2004.03.010 | Abstract: | Several years ago classical Euclidean geometry problems of densest packing of circles in the plane have been formulated as nonconvex optimization problems, allowing to find heuristic solutions by using any available NLP solver. In this paper we try to improve this procedure. The faster NLP solvers use first order information only, so stop in a stationary point. A simple switch from Cartesian coordinates to polar or vice versa, may destroy this stationarity and allow the solver to descend further. Such formulation switches may of course be iterated. For densest packing of equal circles into a unit circle, this simple feature turns out to yield results close to the best known, while beating second order methods by a time-factor well over 100. This technique is formalized as a general reformulation descent (RD) heuristic, which iterates among several formulations of the same problem until local searches obtain no further improvement. We also briefly discuss how RD might be used within other metaheuristic schemes. |
Keywords: | Circle packing | Global optimization | Metaheuristics | Minos | Reformulation descent | Publisher: | Elsevier | Project: | Serbian Ministry of Sciences, Project 1583 |
Show full item record
SCOPUSTM
Citations
79
checked on Dec 23, 2024
Page view(s)
19
checked on Dec 23, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.