Reformulation descent applied to circle packing problems

详细信息    查看全文

• 作者：Mladenovic ; Nenad ; Plastria ; Frank ; Uro&scaron ; evic ; Dragan
• 关键词：Global optimization ; Circle packing ; Metaheuristics ; Reformulation descent ; Minos
• 刊名：Computers and Operations Research
• 出版年：2005
• 出版时间：September, 2005
• 年：2005
• 卷：32
• 期：9
• 页码：2419-2434
• 全文大小：299 K

文摘

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.