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.

円と長方形の詰込み問題とは, 与えられたいくつか円と長方形を重複なく詰込むことができる最小円を求める問題である. 本研究では, この問題を詰込んだ円と長方形たちの重心と最小円の中心が一致するという条件の下で考える. 本論文ではこの問題を混合整数DC計画問題として定式化を行い, 混合整数DCアルゴリズムを適用した実験結果について報告する.

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.