Reformulation descent applied to circle packing problems

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.