Discretization-based solution approaches for the circle packing problem

We consider the problem of packing a set of circles into the smallest containing circle. This problem can be cast as a nonconvex quadratically constrained program, and difficult to solve in general. We provide an iterative solution approach based on a bisection-type algorithm on the radius of the container. Our algorithm is based on discretizing the container into small cells, and solves restricted and relaxed versions of the problem as mixed-integer linear programs. We enhance our algorithm with solution space reduction, bound tightening and variable elimination techniques. We obtain promising results compared to global solvers and heuristic methods from literature.