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