Group for Research in Decision Analysis


Reformulation Descent Applied to Circle Packing Problems

, , and

In this note we explore the fact that a stationary point of some nonlinear non-convex optimization problem is not always a local optimum, and that such a stationary point with respect to one formulation does not necessarily remain stationary for another formulation. Therefore, escaping from a stationary point is possible by changing the formulation of the problem. This approach, that we call Reformulation descent (RD), is introduced here as a more generally applicable heuristic, and illustrated for circle packing problems, where transformations of the coordinates (from cartesian to polar and vice versa) are used in the reformulation. This simple feature turns out to yield results close to the best known. We also briefly discuss extensions of the RD idea that suggests a new meta-heuristic for solving combinatorial and global optimization problems, called Reformulation search.

, 19 pages

This cahier was revised in March 2004