Lindo Systems

!  Circle packing:
  We want to pack n circles, 
  each of the same radius r,
  inside a larger circle of radius = 1.
  We want to maximize r;
! Keywords: Packing, Circle Packing, Puzzle;
sets:
 circ: x, y; ! The x,y coordinate of each circle;
endsets
 data:
 ! Turn on Global solver to get good answers.
 ! Best known solutions:
   Ref. Kravitz, S. "Packing Cylinders into Cylindrical Containers."
        Math. Mag. 40, 65-70, 1967.
     n       r
     1       1
     2      .5
     3     0.4641016  = 1/(1+2*(3^0.5)/3)
     4     0.4142135  = 1/(1 + 2^0.5)
     5     0.3701908  = 1/(1+(2*(1+(5^(-0.5))))^0.5)
     6     0.3333333  = 1/3
     7     0.3333333  = 1/3
     8     0.3025934  = 1/(1+ 1/@sin((3.141592654/7)))
     9     0.2767685  = 1/(1+(2*(2+(2^0.5)))^0.5)
    10     0.26222
    11     0.2548547  = 1/(1 + 1/@SIN(3.141592654/9))
    12     0.2482    (best known)
    13     0.236068   = 1/(1 + 1/@SIN(3.141592654/10))
    14     0.23105   (best known)
    15     0.22117253909  ( best known)
    16     0.21666   (best known)
    17     0.20866   (best known)
    18     0.2056046 (best known) = 1/(1+2^0.5 + 6^0.5)
    19     0.2056046 (best known) = 1/(1+2^0.5 + 6^0.5)
    20     0.19522   (best known)

   For large n, the optimal r will
  approach and be <= ((pi/(2*n*3^0.5)))^0.5  = .952313/(n^0.5)
 ;
 circ = 1..21;  ! Number of circles, n;
enddata

max = r;

nc = @SIZE(circ);
@for( circ(i):
  @bnd(-1,x(i),1); @bnd(-1,y(i),1);
! Circle i inside big circle;
  x(i)^2 + y(i)^2 <= (1-r)^2;
! Circles i and j cannot overlap;
 @for( circ(j)| j #GT# i:
    (x(i) - x(j))^2 + (y(i) - y(j))^2 >= 4*r^2;
     );
    );

! Kill some symmetry;
 x(1) = 0;  ! Can always rotate about z axis to get this;
 x(2) >= 0; ! Can rotate about y axis to get this;
 @for( circ(i): ! Can arbitrarily number from low to high;
  @for( circ(j)| j #GT# i:
     y(i) <= y(j); ! Order circles low to high;
     );
    );