Lindo Systems

! Maximize the area of a polygon having n points such
that the distance between any pair is <= 1.
Based on an example of D. Gay.
Notes:
  1) This does not mean that the polygon will
     fit inside a circle of diameter 1,
  2) For n odd, there may be multiple local optima.
For;
! Keywords: Polygon;
sets:
 point: rho, theta;
endsets
data:
 ! Best known solutions:
      n     Area
      3   0.4330127
      4   0.5 
      5   0.657164
      6   0.674981;
 ! Note, the area of a unit diameter
   circle is 0.7853982;
 point = 1..5;
enddata

 n = @size(point);

! Partition the polygon into triangles, each with
  an apex at point n and
  maximize the sum of their areas;
max = .5*@sum( point(i) | i #gt# 1:
         rho(i)*rho(i-1)*@sin(theta(i)-theta(i-1));

             );
@for( point(i):
   rho(i) <= 1;
   @BND( 0, theta(i), @PI());
     );

! Points i and j can be at most 1 apart;
@for( point(i)| i #lt# n:
  @for( point(j)| j #gt# i:
     [Dist]      rho(i)^2 + rho(j)^2 
       - 2*rho(i)*rho(j)*@cos(theta(j) - theta(i)) <= 1
      );  
    );

! They must be ordered;
 @for( point(i) | i #gt# 1:
     theta(i) >= theta(i-1)
     );

! Kill some symmetry;
   theta(n) = @PI();
     rho(n) = 0;