Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\'o}pez et.al. The problem is to pack circles of unequal size into a fixed size circular container, so as to maximize the total area of the packed circles. L{\'o}pez et al.\! formulated this problem as a mixed-integer nonconvex quadratic programming problem, and proposed a heuristic method based on its continuous relaxation, by which they were able to solve instances with up to 40 circles. Here we propose heuristic algorithms using mixed-integer DC programming. A DC program is an optimization problem in which the objective function can be represented by the difference of two convex functions, and a mixed-integer DC program is a DC program where some of the variables are restricted to integer values. By our method, we were able to obtain good solutions for problems with up to 60 circles.

## Citation

Tokyo University of Science, 6-3-1 Niijuku, Katsushika-ku, Tokyo 125-8585, Japan, Feb/2019

## Article

View Algorithms for the circle packing problem based on mixed-integer DC programming