circle packing

On tackling reverse convex constraints for non-overlapping of unequal circles

  • Chrysanthos E. Gounaris
  • Akang Wang
    • Categories Global Optimization, Global Optimization Applications Tags , , , , ,

    We study the unequal circle-circle non-overlapping constraints, a form of reverse convex constraints that often arise in optimization models for cutting and packing applications. The feasible region induced by the intersection of circle-circle non-overlapping constraints is highly non-convex, and standard approaches to construct convex relaxations for spatial branch-and-bound global optimization of such models typically yield … Read more

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

  • Yoshiko Ikebe
  • Satoru Masuda
  • Takayuki Okuno
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    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 … Read more

    On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

  • Alberto Costa
  • Pierre Hansen
  • Leo Liberti
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more

    Solving the problem of packing equal and unequal circles in a circular container

  • Andrea Grosso
  • Marco Locatelli
  • Jalal Uddin Abdur Jamali
  • Fabio Schoen
    • Categories Stochastic Approaches Tags , ,

    In this paper we propose a Monotonic Basin Hopping approach and its population-based variant Population Basin Hopping to solve the problem of packing equal and unequal circles within a circular container with minimum radius. Extensive computational experiments have been performed both to analyze the problem at hand, and to choose in an appropriate way the … Read more

    Efficiently packing unequal disks in a circle: a computational approach which exploits the continuous and combinatorial structure of the problem

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization Tags , , , ,

    Placing $N$ non-overlapping circles in a smallest container is a well known, widely studied problem that can be easily formulated as a mathematical programming model. Solving this problem is notoriously extremely hard. Recently a public contest has been held for finding putative optimal solutions to a special case in circle packing. The contest saw the … Read more

    Disk Packing in a Square: A New Global Optimization Approach

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Stochastic Approaches Tags , , , , ,

    We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we … Read more

    Packing circles in a square: new putative optima obtained via global optimization

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Global Optimization Applications, Stochastic Approaches Tags , ,

    The problem of finding the optimal placement of $N$ identical, non overlapping, circles with maximum radius in the unit square is a well known challenge both in classical geometry and in optimization. A database of putative optima is currently maintained at \url{www.packomania.com}. Recently, through clever use of an extremely simple global optimization method, we succeeded … Read more

    Test problems of circles in circle packing with behavior constraint and known the optimal solutions

  • Che Chao
  • Teng Hong-fei
  • Wang Yi-Shou
  • Chen Yu
    • Categories Combinatorial Optimization Tags , , , ,

    Test problems are generally used to effectively evaluate the algorithms for packing problem. Based on the engineering background of the layout optimization for a retrievable satellite module, this paper describes the test problems for circles packing problem with known optimization solution first. There are N(≦217) circular objects, different in size, packed in a circular container … Read more