cpack.gms : Packing identical size circles in the unit circle

Description

Given the unit circle (of radius 1), find a set of identical
size circles with an optimized (maximal) radius r so that all
such circles are contained by the unit circle, in a non-overlapping
arrangement.

A test example from  the LGO library


Reference

  • Pinter, J D, Nonlinear optimization with GAMS/LGO. Journal of Global Optimization 38, 1 (2007), 79-101.

Small Model of Type : QCP


Category : GAMS Model library


Main file : cpack.gms

$title Packing identical size circles in the unit circle (CPACK,SEQ=387)
$ontext
Given the unit circle (of radius 1), find a set of identical
size circles with an optimized (maximal) radius r so that all
such circles are contained by the unit circle, in a non-overlapping
arrangement.

A test example from  the LGO library


Pinter, J D, Nonlinear optimization with GAMS/LGO. 
Journal of Global Optimization 38 (2007), 79-101.
$offtext

$if not set k $set k 5
Sets i / i1 * i%k% /;
alias (i,j);

* Here we define the set ij(i,j) of ordered pairs i,j i<j.
Set ij(i,j); ij(i,j)$(ord(i)<ord(j)) = yes;

Variables
     r     radius of identical sized circles
     x(i)  x coordinate of circle i
     y(i)  y coordinate of circle i;

Equations
     circumscribe(i) Enforce circle is enclose in unit circle
     nooverlap(i,j)  Enforce that circles do not overlap;

circumscribe(i)..    sqr(1-r) =g= sqr(x(i)) + sqr(y(i));
nooverlap(ij(i,j)).. sqr(x(i)-x(j))+sqr(y(i)-y(j)) =g= 4*sqr(r);

x.lo(i) = -1; x.up(i) = 1;
y.lo(i) = -1; y.up(i) = 1;

* starting values for local solvers such that some feasible solution is produced (at least with k=5)
x.l(i) = -0.2 + ord(i) * 0.1;
y.l(i) = -0.2 + ord(i) * 0.1;

* These bound are valid for k>=5
r.lo = 0.05; r.up = 0.4;

model m /all/;
solve m using qcp maximizing r;
display r.l;