We consider the problem of packing congruent circles with the maximum radius in a unit square. As a mathematical program, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem which possesses a large number of local optima. We study several convexification techniques for the circle packing problem, including polyhedral and semi-definite relaxations and assess their strength theoretically. As we demonstrate both theoretically and numerically, when embedded in branch-and-cut based global solvers, the current state-of-the-art bounding techniques are only effective for small-size circle packing problems.
Citation
Under review.
Article
View Packing circles in a square: a theoretical comparison of various convexification techniques