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