# Maximum area for unit-diameter polygon (Prieto's second model).

# This derives from a GAMS model by Francisco J. Prieto -- the second
# one in E-mail that he sent to Margaret Wright.  Prieto described
# this as "a very particular solution for the problem, taking advantage
# of [a] certain property that I [Prieto] am convinced (although I cannot
# prove it) that the solution must have.  The formulation
# is much more efficient, and you can go up to sizes of around 70-80.

# "Symmetry is assumed (so the size is reduced to a half), and also as
# many constraints as possible are set up as equalities.

# "The results obtained seem to coincide (within some error margin) with
# the ones obtained from the previous program."


param N 'number of sides' integer > 1;
	check: N == 2*floor(N/2);	# Make sure N is even.

param Lsup := N/2 - 1;

set I := 1..Lsup;

var x{I} >= 0, <= 1, := .5;		#first (Cartesian) coordinate

var y{i in I} >= 0, <= 1, := i/Lsup;	#second (Cartesian) coordinate

# distance constraints (tight)
s.t. cd{i in ceil(Lsup/2) .. Lsup, j in max(1, Lsup-i) .. min(Lsup+1-i, i)}:
	(x[i] + x[j])**2 + (y[i] - y[j])**2 == 1;

# extra distance constraint
s.t. extr: x[Lsup]^2 + y[Lsup]^2 == 1;

# second coordinate constraint (ordered values)
s.t. ory{i in 2..Lsup}: y[i] >= y[i-1];

maximize area: sum{i in 2..Lsup-1} y[i]*(x[i-1]-x[i+1])  +
		x[Lsup] + y[Lsup]*x[Lsup-1] - x[2]*y[1];

data;
param N :=

# This assumes that N will be given separately.  For example,
# you might invoke
#    ampl -omp20 p2gon.mod -
# and then type
#    20; end;
# to generate the 20-sided version of this problem (in files p20.*).