! LINGO model for
Rectangular 2D cutting stock with guillotine cuts.
Given:
Raw material master rectangle of dimensions x1 by y1,
and finished good (f.g.) rectangles i, of dimensions dx(i) by dy(i),
Find a sequence of guillotine cuts x(j) and y(j), so as to
maximize the value of the f.g. rectangles cut from the master.
Cutting process is viewed as a binary tree, with
node i having the two children: 2*i and 1+2*i.
Each cut splits a rectangle into two smaller
rectangles. Material may be isotropic, (rotate = 1)such as glass,
so finished good may be rotated 90 degrees, or
non-isotropic (rotate = 0) such as a heavily grained wood;
! Keywords: Cutting stock, Guillotine cut, Two-dimensional cutting stock;
SETS:
piece: x, y, uflag;
fg: dx, dy, v, nc, nr;
pxf(piece, fg): zn, zr;
ENDSETS DATA:
! Raw material dimensions. Standard window glass;
x1 = 84; y1 = 72; ! The raw material;
! Finished good dimensions, and their values, and max number copies useful;
fg dx dy v nc =
w1 35 41 1 2
w2 16 43 1 1
w3 36 18 1 1
w4 36 19 1 1
w5 35 14 1 1
w6 37 13 1 1
w7 43 19 1 2
w8 23 35 1 1;
! Optimal obj = 8 if rotation is allowed,
= 7 if no rotation allowed;
! Number of nodes in tree, should be of order
2^(number of cuts);
piece = 1..127;
! Set rotate = 1 if rotation allowed (isotropic),
= 0 otherwise (non-isotropic);
rotate = 1;
ENDDATA
! Maximize the value of fg's assigned.
zn(i,j) = 1 if final node i is assigned non-rotated fg j.
zr(i,j) = 1 if final node i is assigned rotated fg j,
x(i) = horizontal dimension of the piece at node i,
y(i) = vertical dimension of the piece at node i;
! This model is useful for modest size problems, e.g., < 8 fg's.
Thereafter, solution time increases rapidly with problem size;
SUBMODEL GENGPAT:
MAX = @SUM(pxf(i,j)| i #ge# 64: v(j)*(zn(i,j)+ zr(i,j)));
! The z(i,j)'s are binary;
@FOR(pxf(i,j):
@BIN(zn(i,j)); @BIN(zr(i,j));
zr(i,j) <= rotate;
);
! The first node is the original raw material;
x(1) = x1; y(1) = y1;
! We make horizontal cuts to get to these nodes;
@FOR( piece(i)| ( i #ge# 2 #and# i #lt# 4) #or#
( i #ge# 8 #and# i #lt# 16) #or#
( i #ge# 32 #and# i #lt# 64):
[H1] x(i) = x(@FLOOR(i/2));
@FOR(piece(i1)| i1 #eq# i #and# i #eq# 2*@FLOOR(i/2):
[HT] y(i) + y( i+1) = y(i/2);
! Kill some symmetry, Force the lower, even-numbered
twin to be the bigger one;
[HS] y(i) >= y(i/2)/2;
);
);
! We make vertical cuts to get to these nodes;
@FOR( piece(i)| ( i #ge# 4 #and# i #lt# 8) #or#
( i #ge# 16 #and# i #lt# 32) #or#
( i #ge# 64 #and# i #lt# 128):
[V1] y(i) = y(@FLOOR(i/2));
@FOR(piece(i1)|i1 #eq# i #and# i1 #eq# 2*@FLOOR(i/2):
[VT] x(i) + x( i+1) = x(i/2);
! Kill some symmetry;
[VS] x(i) >= x(i/2)/2;
);
);
! A finished good can be assigned only to a terminal node;
@SUM(pxf(i,j)| i #lt# 64: zn(i,j)+zr(i,j)) = 0;
@FOR( piece(i)| i #ge# 64:
! At most one finished good to a node;
[FN] @SUM( pxf(i,j): zn(i,j)+zr(i,j)) <= 1;
);
! Each finished good assigned at most nc(j) times;
@FOR( fg(j):
[F1] @SUM( pxf(i,j): zn(i,j)+zr(i,j)) = nr(j);
@BND( 0, nr(j), nc(j));
);
@FOR( piece(i) | i #ge# 64:
! If piece i satisfies fg j with no rotation, then dimensions match;
[N1] x(i) >= @SUM( fg(j): dx(j)*zn(i,j));
[N2] y(i) >= @SUM( fg(j): dy(j)*zn(i,j));
[N3] x(i) <= x1 - @SUM( fg(j): (x1-dx(j))*zn(i,j));
[N4] y(i) <= y1 - @SUM( fg(j): (y1-dy(j))*zn(i,j));
! If piece i satisfies fg j with rotation, then dimensions match;
[R1] y(i) >= @SUM( fg(j): dx(j)*zr(i,j));
[R2] x(i) >= @SUM( fg(j): dy(j)*zr(i,j));
[R3] y(i) <= y1 - @SUM( fg(j): (y1-dx(j))*zr(i,j));
[R4] x(i) <= x1 - @SUM( fg(j): (x1-dy(j))*zr(i,j));
);
! Some cuts;
! Knapsack, from which further cuts can be derived.
The area of rectangles produced must be <= area of raw material;
@SUM(pxf(i,j): dx(j)*dy(j)*(zn(i,j) + zr(i,j))) <= x1*y1;
! Kill some symmetry.
The bigger width must be assigned to the lower twin;
@FOR( pxf(i,j)| i #ge# 64 #AND# i #eq# 2*@FLOOR(i/2):
@SUM(fg(j): dx(j)*zn(i,j) + dy(j)*zr(i,j)) >=
@SUM(fg(j): dx(j)*zn(i+1,j) + dy(j)*zr(i+1,j))
);
ENDSUBMODEL
CALC:
@SOLVE( GENGPAT);
! Set uflag(i) > 1 if any fg cut from subrectangle i;
@FOR( PIECE(i): uflag(i) = 0);
iset = @SIZE( PIECE);
@FOR( PIECE(i) | i #GT# 1:
@IFC( iset #GE# 64:
uflag(iset) = @SUM( fg(j) : j*(zn(iset,j)+zr(iset,j)));
);
parent = @FLOOR( iset/2);
uflag(parent) = uflag(parent)+uflag(iset);
iset = iset -1;
);
@WRITE(' Cut Parent ', @NEWLINE(1));
@WRITE(' type Rectangle rect. X Y', @NEWLINE(1));
@WRITE(' 1 - ',@FORMAT(x1,"5.1f"),' ',@FORMAT( y1,"5.1f"), @NEWLINE(1));
@FOR( piece(i)| i #GT# 1 #AND# uflag(i) #GT# 0:
parent = @FLOOR(i/2);
@IFC(( i #ge# 2 #and# i #lt# 4) #or#
( i #ge# 8 #and# i #lt# 16) #or#
( i #ge# 32 #and# i #lt# 64):
! We make horizontal cuts to get to these nodes;
@IFC( y(i) #GT# 0 #AND# x(i) #GT# 0: ! Is it a non-trivial cut...;
@WRITE( ' H ', @FORMAT(i,"3.0f"),' ',@FORMAT(parent,"3.0f"),
' ',@FORMAT(x(i),"5.1f"),' ',@FORMAT(y(i),"5.1f"),@NEWLINE(1));
);
@ELSE
@IFC( x(i) #GT# 0 #AND# y(i) #GT# 0: ! Is it a non-trivial cut...;
@WRITE( ' V ', @FORMAT(i,"3.0f"),' ',@FORMAT(parent,"3.0f"),
' ',@FORMAT(x(i),"5.1f"),' ',@FORMAT(y(i),"5.1f"));
@IFC( i #GE# 64:
@WRITE(' ',fg(uflag(i)),@NEWLINE(1));
@ELSE
@WRITE(@NEWLINE(1));
);
);
);
);
ENDCALC
|