****************************************************************** ****************************************************************** * * 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 ****************************************************************** ****************************************************************** $Title Full discrete space MILP model and search algorithm for 2-D strip packing problem $eolcom # SETS I Items /I1*I50/ X Strip width /X1*X300/ Y Strip height /Y1*Y300/ IT Iterations /IT1*IT100/ ACTI(I) Active items ACTW(X) Active width points ACTH(Y) Active heigth points INICIO(X) Origin of the grid X axis POSO(I,X,Y) Possible origin points for item I ; ALIAS(I,IL); ALIAS(X,XL,XLL); ALIAS(Y,YL,YLL); SCALAR TCPU Total computational time CPUs /7200/ SCALAR STRIPW Strip width; SCALAR STRIPH Strip height; SCALAR LB Continuous lower bound SCALAR AUX Auxiliary parameter /0/ PARAMETERS WIDTH(I) Width of item I HEIGHT(I) Heigth of item I ; PARAMETERS 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,I20 1,I21 1/ 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,I20 9,I21 9/; STRIPW=10; # Strip width ACTI(I)=yes$(WIDTH(I) GT 0); INICIO(X)=yes$(ord(X) EQ 1); LB=SUM(I$(ACTI(I)),WIDTH(I)*HEIGHT(I)/STRIPW); STRIPH=MAX(CEIL(ROUND(SUM(I$(ACTI(I)),WIDTH(I)*HEIGHT(I)/STRIPW),3)),SMAX(I$(ACTI(I)),HEIGHT(I))); ACTW(X)=yes$(ord(X) LE STRIPW); ACTH(Y)=yes$(ord(Y) LE STRIPH); 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); display ACTI,ACTW,ACTH,STRIPH,POSO,WIDTH,HEIGHT,LB; BINARY VARIABLES N(I,X,Y) Origin of item I is placed on grid element with coordinates X and Y POSITIVE VARIABLES ER(X,Y) Excess resource of point with coordinates X and Y; VARIABLES OBJ Objective function; EQUATIONS OBJECT Place items as close as possible to grid origin BALREC(X,Y) Excess resource balance for point with coordinates X and Y EXTRA(I) Every item needs to be placed on the grid; OBJECT.. OBJ=e=SUM((I,X,Y)$(POSO(I,X,Y)),N(I,X,Y)*(ord(X)+ord(Y)-2)); 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)); EXTRA(I)$(ACTI(I)).. SUM((X,Y)$(POSO(I,X,Y)),N(I,X,Y))=e=1; #ER.up(X,Y)=0; #Add for perfect packing OPTION optcr=1E-6; OPTION optca=0.999; OPTION limrow=0; OPTION limcol=0; OPTION Solprint=Off; OPTION iterlim=50000000; OPTION reslim=7200; MODEL SP2D using /OBJECT,BALREC,EXTRA/; AUX=0; loop(IT$(AUX NE 1 and TimeElapsed