! Pack circles into a rectangle; 
! Keywords: Packing, Pallet, Circle packing;
SETS:
  circ: x, y, rad, val, z;
  cxc( circ, circ) | &1 #LT# &2: zz;
ENDSETS
DATA: ! A standard U.S. shipping pallet is 40" by 48". We want to maximize the value of a set of barrels placed upright on such a pallet; xw = 40; ! X width of rectangle; yw = 48; ! Y width of rectangle; ! Radius and value of circles to pack; rad, val = 4 1 8 2 11 3 13 3 15 4 20 5; ENDDATA ! Variables: z(i) = 1 if circle i is packed, else 0, zz(i,j) = 1 if both circles i and j are packed, x(i) = x coordinate of center of circle i if packed, y(i) = y coordinate of center of circle i if packed; ! Maximize value of circles packed; MAX = @SUM( circ(j): val(j)*z(j)); ! zz(i,j) = 1 if both i and j are packed; @FOR( cxc(i,j): zz(i,j) >= z(i) + z(j) - 1; zz(i,j) <= z(i); zz(i,j) <= z(j); ); ! If both circles i and j are packed, they cannot overlap; @FOR( cxc(i,j): (x(i) - x(j))^2 + (y(i) - y(j))^2 >= zz(i,j)*(rad(i)+rad(j))^2; ); ! If circle i is packed, it must be within the rectangle; @FOR( circ(i): x(i) >= rad(i)*z(i); x(i) <= (xw - rad(i))*z(i); y(i) >= rad(i)*z(i); y(i) <= (yw - rad(i))*z(i); @BIN(z(i)); ); ! Some optional cuts to reduce the search space; ! Reduce symmetry; ! By rotating the rectangle around the Y axis, we can always guarantee that ...; x(1) <= x(2); ! By rotating the rectangle around the X axis, we can always guarantee that...; y(1) <= y(2); ! Area of circles packed must be < area of rectangle; @PI()*@SUM( circ(i): z(i)*rad(i)^2) <= xw*yw;