******************************************************************************* * * Cutting stock example illustrating column generation. * * Numbers for m=3 are from Exercise 1.14 in course 5B1814. * * Gams model written by Anders Forsgren, November 8 2001. * ******************************************************************************* options lp=xpress; options mip=cplex; options limcol=0; options optcr=0; * Actual number of different widths scalar m / 3 /; * Define the sets of widths and columns sets imax maximum number of different widths / i1*i20 / i(imax) actual number of different widths jmax maximum number of columns / j1*j100 / j(jmax) actual number of columns; * Define i and j as first m components of imax and jmax i(imax) = no; i(imax)$(ord(imax) le m) = yes; j(jmax) = no; j(jmax)$(ord(jmax) le m) = yes; * Define the m widths parameter w(imax) / i1 2 i2 3 i3 4 /; * Define the m requirements parameter b(imax) / i1 35 i2 30 i3 4 /; * Define the width of the roll scalar WW / 11 /; * The constraint matrix parameter A(imax,jmax); * Initialize the constraint matrix to a multiple of the identity matrix loop(imax$i(imax), A(imax,jmax)$(ord(jmax) eq ord(imax)) = floor(WW/w(imax)); ); * Set the tolerance parameter tol; tol = 0.0000001; * Master problem variables zmaster objective of master problem x(jmax) number of rolls to be cut from cut pattern j; positive variable x; equations objmaster objective of master problem satdem(imax) satisfy demand; objmaster .. sum(j,x(j)) =e= zmaster; satdem(i) .. sum(j,A(i,j)*x(j)) =g= b(i); model master / objmaster, satdem /; * Subproblem variables zsub objective of subproblem aj(imax) cut pattern ; integer variable aj; equations objsub objective of subproblem j knapcons ; parameter y(imax); objsub .. 1 - sum(i,y(i)*aj(i)) =e= zsub; knapcons .. sum(i,w(i)*aj(i)) =l= WW; model sub / objsub, knapcons /; * Loop zsub.l = -tol-1; alias(iter,jmax); loop(iter$(zsub.l lt -tol and ord(iter) gt m and ord(iter) lt card(jmax)), solve master using lp minimizing zmaster; y(i) = satdem.m(i); solve sub using mip minimizing zsub; A(i,iter) = aj.l(i); j(iter) = yes; ); * Display result parameter Acut(imax,jmax); Acut(imax,jmax)$(i(imax) and x.l(jmax)) = A(imax,jmax); parameter xcut(jmax); xcut(jmax)$(x.l(jmax)) = ceil(x.l(jmax)); scalar maxdiff; maxdiff = sum(j,xcut(j)) - sum(j,x.l(j)); display Acut, x.l, xcut, maxdiff;