Optimization Online


Algorithms for the circle packing problem based on mixed-integer DC programming

Satoru Masuda(okunotakayuki***at***gmail.com)
Yoshiko Ikebe(yoshiko***at***rs.tus.ac.jp)
Takayuki Okuno(takayuki.okuno.ks***at***riken.jp)

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{\'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.

Keywords: Circle packing, Nonlinear optimization, Mixed integer DC programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- OR and Management Sciences

Citation: Tokyo University of Science, 6-3-1 Niijuku, Katsushika-ku, Tokyo 125-8585, Japan, Feb/2019

Download: [PDF]

Entry Submitted: 02/14/2019
Entry Accepted: 02/15/2019
Entry Last Modified: 02/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society