Lindo Systems

! 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;