Search

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.

In this paper, we consider a class of mixed integer programming problems (MIPs) whose objective functions are DC functions, that is, functions representable in terms of a difference of two convex functions, and particularly focus on the nonconvex case. Recently, Maehara, Marumo, and Murota provided a continuous reformulation without integrality gaps, for discrete DC programs having only integral variables. They also presented a new algorithm to solve the reformulated problem. Our aim is to extend their results to MIPs and further give a new algorithm to solve them. Specifically, we propose an algorithm based on DCA originally proposed by Pham Dinh and Le Thi, where convex MFs are solved iteratively.