circpack.gms : Pack circles in the smallest possible rectangle

Description

For a given set of circles determine the minimum area rectangle which hosts
all circles.

The problem requires a global solver.


Small Model of Type : NLP

Category : GAMS Model library

Main file : circpack.gms

$title Pack Circles in the smallest possible Rectangle (CIRCPACK,SEQ=401)$onText
For a given set of circles determine the minimum area rectangle which hosts
all circles.

The problem requires a global solver.

Kallrath, J. Cutting Circles and Polygons from Area-Minimizing Rectangles.
Journal of Global Optimization 43 (2009), 299-328

Keywords: nonlinear programming, global optimization, cutting stock problem,
circle packing problem, shape constraints, non-overlap constraints,
design problem
$offText Set d 'dimensions' / 1, 2 / i 'items=circles' / i1*i6 /; Parameter sizeLB(d) 'lower bounds on rectangle size' / 1 1, 2 1 / sizeUB(d) 'upper bounds on rectangle size' / 1 4, 2 8 / R(i) 'radius of circles' / i1 1.2, i2 0.6, i3 0.8 i4 1.7, i5 1.3, i6 0.5 /; *----------------------------------------------------- * The NLP model for solving the circle packing problem *----------------------------------------------------- Alias (i,ii); Variable a 'area of the rectangle' xP(d) 'the width (d=1) and length (d=2) of the rectangle' x(i,d) 'the center of circle i' z 'objective function'; Positive Variable a, xP, x; Equation objective 'trimloss' area 'the area of the rectangle' disjun(i,ii) 'non-overlap condition for the circles' ULx(i,d) 'upper limit on x(i) le w - R(i)'; objective.. z =e= a - sum(i, pi*sqr(R(i))); * compute the area of the design rectangle (bilinear version) area.. a =e= prod(d, xP(d)); * upper limit on the coordinates of the center of the circles ULx(i,d).. x(i,d) =l= xP(d) - R(i); * DISJUN(i,ii)$(not sameas(i,ii))..
disjun(i,ii)$(i.pos > ii.pos).. sum(d, sqr(x(i,d)-x(ii,d))) =g= sqr(R(i)+R(ii)); Model Circpack / all /; * lower and upper bounds on the centre of the circles x.lo(i,d) = R(i); x.up(i,d) = sizeUB(d) - R(i); * upper bound on the area a.up = prod(d,sizeUB(d)); * upper bounds on the width and length of the rectangle xP.up(d) = sizeUB(d); * A simple scheme (such as below) for setting the starting point does not * lead to a feasible solution when using a local solver. This problem requires * a global code x.l(i,d) = uniform(x.lo(i,d), x.up(i,d)); xP.l(d) = sizeUB(d); a.l = a.up; option resLim = 60, optCr = 0; solve Circpack using nlp minimizing z; display a.l, xP.l, z.l, x.l; * produce some nice looking output$ifThen set gnuplot
*  create the output file: result.out which can be fed into GnuPlot
File fresultout / result.out /;
put  fresultout;
put ' output ' /
'set parametric' /
'set trange [0:',(2*PI):11:8,']' /
@21, ' plot ';
loop(i,
put x.l(i,"2"):4:2,'+',R(i):4:2,'*cos(t),', x.l(i,"1"):4:2,'+',R(i):4:2,'*sin(t),';
);
put ' ' /;
put ' ' /;
put ' Verschnitt in qm : ', (a.l - sum(i, R(i))):5:2 /;
$endIf$ifThen set latex
*  produce tex output-file to show the result
*  create the output file: graphics.tex
File fgraphics / graphics.tex /;
put  fgraphics;
$onPut %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % "graphics.tex" % % written by Josef Kallrath and Steffen Rebennack % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass{article} \usepackage{pst-all} % \begin{document} % \pagestyle{empty} \centering \begin{figure}$offPut

*  calculate the size of the figure
*  -> find out the maximum coordinates
Scalar
maxX 'maximum x coordinate'
maxY 'maximum y coordinate'
step '1 pt is step cm in the picture';

maxX = smax(i, x.l(i,"2") + R(i));
maxY = smax(i, x.l(i,"1") + R(i));
step = 20/(max(maxX,maxY) + 2);

*  print the size of the figure
put '    \psset{xunit=' ,  step:4:2 , 'cm,yunit=' ,  step:4:2 , 'cm}' /
'    \begin{pspicture}(0,0)(' , maxX:4:0 , ','  , maxY:4:0 , ')' /
'      \psaxes{<->}' , '(0,0)(-.5,-.5)(' , maxX:4:0 , ',' , maxY:4:0 , ')' /
'      % ' /;

*  print all circles
loop(i,
put  '      \psellipse[linewidth=1pt,linecolor=black]'
'(' , x.l(i,"2"):4:2 , ',' , x.l(i,"1"):4:2 , ')'
'(' , R(i):4:2 , ',' ,  R(i):4:2 , ')' /;
);
put '      % ' /;

*  draw rectangle
put  '      \psline[linewidth=1pt,linecolor=blue]'
'(' , 0:6:2 , ',' , 0:6:2, ')'
'(' , xP.l('2'):6:2 , ',' , 0:6:2, ')' /
'      \psline[linewidth=1pt,linecolor=blue]'
'(' , xP.l('2'):6:2 , ',' , 0:6:2, ')'
'(' , xP.l('2'):6:2 , ',' , xP.l('1'):6:2, ')' /
'      \psline[linewidth=1pt,linecolor=blue]'
'(' , xP.l('2'):6:2 , ',' , xP.l('1'):6:2, ')'
'(' , 0:6:2 , ',' , xP.l('1'):6:2, ')' /
'       \psline[linewidth=1pt,linecolor=blue]'
'(' , 0:6:2 , ',' , xP.l('1'):6:2, ')'
'(' , 0:6:2 , ',' , 0:6:2, ')' /;

put '      %' /
'    \end{pspicture}' /
'  \end{figure}' /
'  %' /
'\end{document}' /;

*  produce a PostScript and a PDF file (works only with a LaTeX compiler)
execute 'latex graphics.tex && dvips graphics.dvi && ps2pdf graphics.ps';
execute 'rm -f graphics.aux graphics.dvi graphics.log graphics.ps';
\$endIf

GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170