# 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.*).