Algorithms for the circle packing problem based on mixed-integer DC programming (New Trends of Numerical Optimization in Advanced Information-Oriented Society)

Abstract

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ó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ó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. In this paper, we propose an algorithm 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.