TY - JOUR

T1 - MIXED-INTEGER DC PROGRAMMING BASED ALGORITHMS FOR THE CIRCULAR PACKING PROBLEM

AU - Ikebe, Yoshiko

AU - Masuda, Satoru

AU - Okuno, Takayuki

N1 - Publisher Copyright:
© The Operations Research Society of Japan.

PY - 2023/7

Y1 - 2023/7

N2 - Circle packing problems are a class of packing problems in which we are to pack a given set of circles into a container with no overlap. In this paper, we focus on a circle packing problem proposed by López and Beasley. The problem is, given a set of unequal circles to choose and pack a subset of them into a fixed size circular container so as to maximize the total area of the packed circles. López and Beasley formulated this problem as a mixed-integer nonconvex quadratic programming problem and proposed a heuristic method based on its continuous relaxation. By using this method they solved instances with up to 40 circles. Here, we propose heuristic algorithms using mixed-integer DC (Difference-of-Convex) programming. A DC program is an optimization problem whose 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. Computational results showed that our method obtained solutions at least as good as the López and Beasley algorithm for the problem data used in their experiments, and good solutions for problems with up to the previously unsolvable size of 60 circles within reasonable computation time.

AB - Circle packing problems are a class of packing problems in which we are to pack a given set of circles into a container with no overlap. In this paper, we focus on a circle packing problem proposed by López and Beasley. The problem is, given a set of unequal circles to choose and pack a subset of them into a fixed size circular container so as to maximize the total area of the packed circles. López and Beasley formulated this problem as a mixed-integer nonconvex quadratic programming problem and proposed a heuristic method based on its continuous relaxation. By using this method they solved instances with up to 40 circles. Here, we propose heuristic algorithms using mixed-integer DC (Difference-of-Convex) programming. A DC program is an optimization problem whose 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. Computational results showed that our method obtained solutions at least as good as the López and Beasley algorithm for the problem data used in their experiments, and good solutions for problems with up to the previously unsolvable size of 60 circles within reasonable computation time.

KW - Discrete optimization

KW - circle packing

KW - mixed integer dc programming

KW - nonlinear optimization

UR - http://www.scopus.com/inward/record.url?scp=85169513139&partnerID=8YFLogxK

U2 - 10.15807/jorsj.66.153

DO - 10.15807/jorsj.66.153

M3 - Article

AN - SCOPUS:85169513139

SN - 0453-4514

VL - 66

SP - 153

EP - 175

JO - Journal of the Operations Research Society of Japan

JF - Journal of the Operations Research Society of Japan

IS - 3

ER -