****************************************************************** ****************************************************************** * * DOWNLOADED FROM MINLP CYBER-INFRASTRUCTURE * www.minlp.org * * PROBLEM : 2-D Orthogonal Strip Packing * * AUTHOR(S) : Pedro Castro, Jose Oliveira, Ignacio Grossmann * * SUBMITTED BY : Pedro Castro ****************************************************************** ****************************************************************** GAMS Rev 235 WEX-VS8 23.5.2 x86/MS Windows 07/06/11 13:46:06 Page 1 Full discrete space MILP model and search algorithm for 2-D strip packing problem C o m p i l a t i o n 3 4 SETS 5 I Items /I1*I50/ 6 7 X Strip width /X1*X300/ 8 9 Y Strip height /Y1*Y300/ 10 11 IT Iterations /IT1*IT100/ 12 13 ACTI(I) Active items 14 ACTW(X) Active width points 15 ACTH(Y) Active heigth points 16 INICIO(X) Origin of the grid X axis 17 POSO(I,X,Y) Possible origin points for item I 18 ; 19 20 ALIAS(I,IL); 21 ALIAS(X,XL,XLL); 22 ALIAS(Y,YL,YLL); 23 24 SCALAR TCPU Total computational time CPUs /7200/ 25 SCALAR STRIPW Strip width; 26 SCALAR STRIPH Strip height; 27 SCALAR LB Continuous lower bound 28 SCALAR AUX Auxiliary parameter /0/ 29 30 PARAMETERS 31 WIDTH(I) Width of item I 32 HEIGHT(I) Heigth of item I 33 ; 34 35 PARAMETERS 36 WIDTH(I) /I1 2,I2 2,I3 2,I4 2,I5 2,I6 5,I7 5,I8 1,I9 1,I10 10,I11 4,I12 2,I13 2,I14 7,I15 7,I16 7,I17 2,I18 2,I19 2,I 20 1,I21 1/ 37 HEIGHT(I) /I1 3,I2 3,I3 7,I4 7,I5 7,I6 4,I7 4,I8 4,I9 4,I10 1,I11 8,I12 4,I13 4,I14 3,I15 3,I16 3,I17 6,I18 6,I19 6,I2 0 9,I21 9/; 38 39 STRIPW=10; # Strip width 40 41 ACTI(I)=yes$(WIDTH(I) GT 0); 42 INICIO(X)=yes$(ord(X) EQ 1); 43 LB=SUM(I$(ACTI(I)),WIDTH(I)*HEIGHT(I)/STRIPW); 44 STRIPH=MAX(CEIL(ROUND(SUM(I$(ACTI(I)),WIDTH(I)*HEIGHT(I)/STRIPW),3)),SMAX(I$(ACTI(I)),HEIGHT(I))); 45 ACTW(X)=yes$(ord(X) LE STRIPW); 46 ACTH(Y)=yes$(ord(Y) LE STRIPH); 47 POSO(I,X,Y)$(ACTI(I) and ACTW(X) and ACTH(Y))=yes$(ord(X)+WIDTH(I) LE STRIPW+1 and ord(Y)+HEIGHT(I) LE STRIPH+1); 48 49 display ACTI,ACTW,ACTH,STRIPH,POSO,WIDTH,HEIGHT,LB; 50 51 BINARY VARIABLES 52 N(I,X,Y) Origin of item I is placed on grid element with coordinates X and Y 53 54 POSITIVE VARIABLES 55 ER(X,Y) Excess resource of point with coordinates X and Y; 56 57 VARIABLES 58 OBJ Objective function; 59 60 EQUATIONS 61 OBJECT Place items as close as possible to grid origin 62 BALREC(X,Y) Excess resource balance for point with coordinates X and Y 63 EXTRA(I) Every item needs to be placed on the grid; 64 65 OBJECT.. OBJ=e=SUM((I,X,Y)$(POSO(I,X,Y)),N(I,X,Y)*(ord(X)+ord(Y)-2)); 66 BALREC(X,Y)$(ACTW(X) and ACTH(Y)).. ER(X,Y)=e=1-SUM((I,XL,YL)$(ord(XL) GE ord(X)-WIDTH(I)+1 and ord(XL) LE ord(X) and ord( YL) GE ord(Y)-HEIGHT(I)+1 and ord(YL) LE ord(Y) and POSO(I,XL,YL)),N(I,XL,YL)); 67 EXTRA(I)$(ACTI(I)).. SUM((X,Y)$(POSO(I,X,Y)),N(I,X,Y))=e=1; 68 69 #ER.up(X,Y)=0; #Add for perfect packing 70 71 OPTION optcr=1E-6; 72 OPTION optca=0.999; 73 OPTION limrow=0; 74 OPTION limcol=0; 75 OPTION Solprint=Off; 76 OPTION iterlim=50000000; 77 OPTION reslim=7200; 78 79 MODEL SP2D using /OBJECT,BALREC,EXTRA/; 80 81 AUX=0; 82 loop(IT$(AUX NE 1 and TimeElapsed