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
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


checked on May 20, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.