! 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