MODEL:
! Uses Lingo's programming capability to do
on-the-fly column generation for a
cutting-stock problem;
! Keywords: Column Generation, Knapsack Model, Cutting Stock;
SETS:
PATTERN: COST, X;
FG: WIDTH, DEM, PRICE, Y, YIELD;
FXP( FG, PATTERN): NBR;
ENDSETS
DATA:
PATTERN = 1..20; ! Allow up to 20 patterns;
RMWIDTH = 45; ! Raw material width;
FG = F34 F24 F15 F10 F18;!Finished goods...;
WIDTH= 34 24 15 10 18;!their widths...;
DEM = 350 100 800 1001 377;!and demands;
BIGM = 999;
ENDDATA
SUBMODEL MASTER_PROB:
[MSTROBJ] MIN= @SUM( PATTERN( J)| J #LE# NPATS:
COST( J)*X( J));
@FOR( FG( I):
[R_DEM]
@SUM( PATTERN( J)| J #LE# NPATS:
NBR( I, J) * X( J)) >= DEM( I);
);
ENDSUBMODEL
SUBMODEL INTEGER_REQ:
@FOR( PATTERN: @GIN( X));
ENDSUBMODEL
SUBMODEL PATTERN_GEN:
[SUBOBJ] MAX = @SUM( FG( I): PRICE( I)* Y( I));
@SUM( FG( I): WIDTH( I)*Y( I)) <= RMWIDTH;
@FOR( FG( I): @GIN(Y( I)));
ENDSUBMODEL
CALC:
! Set parameters;
@SET( 'DEFAULT');
@SET( 'TERSEO', 2); ! Turn off default output;
! Max number of patterns we'll allow;
MXPATS = @SIZE( PATTERN);
! Make first pattern an expensive super pattern;
COST( 1) = BIGM;
@FOR( FG( I): NBR( I, 1) = 1);
! Loop as long as the reduced cost is
attractive and there is space;
NPATS = 1;
RC = -1; ! Clearly attractive initially;
@WHILE( RC #LT# 0 #AND# NPATS #LT# MXPATS:
! Solve for best patterns to run among ones
generated so far;
@SOLVE( MASTER_PROB);
! Copy dual prices to PATTERN_GEN submodel;
@FOR( FG( I): PRICE( I) = -@DUAL( R_DEM( I)));
! Generate the current most attractive pattern;
@SOLVE( PATTERN_GEN);
! Marginal value of current best pattern;
RC = 1 - SUBOBJ;
! Add the pattern to the Master if it is attractive;
@IFC( RC #LT# 0:
NPATS = NPATS + 1;
@FOR( FG( I): NBR( I, NPATS) = Y( I));
COST( NPATS) = 1;
);
);
! Finally solve Master as an IP;
@SOLVE( MASTER_PROB, INTEGER_REQ);
ENDCALC
! This following calc section displays the
solution in a tabular format;
CALC:
! Compute yield of each FG;
@FOR( FG( F): YIELD( F) =
@SUM( PATTERN( J)| J #LE# NPATS:
NBR( F, J) * X(J))
);
! Compute some stats;
TOTAL_FT_USED = @SUM( PATTERN: X) * RMWIDTH;
TOTAL_FT_YIELD = @SUM( FG: YIELD * WIDTH);
PERC_WASTE = 100 * ( 1 - ( TOTAL_FT_YIELD / TOTAL_FT_USED)) ;
! Display the table of patterns and their usage;
FW = 6;
@WRITE( @NEWLINE( 1));
@WRITE( ' Total raws used: ', @SUM(PATTERN: X) , @NEWLINE( 2),
' Total feet yield: ', TOTAL_FT_YIELD , @NEWLINE( 1),
' Total feet used: ', TOTAL_FT_USED , @NEWLINE( 2),
' Percent waste: ', @FORMAT( PERC_WASTE, '#5.2G'), '%', @NEWLINE( 1));
@WRITE( @NEWLINE( 1), 24*' ', 'Pattern:', @NEWLINE( 1));
@WRITE( ' FG Demand Yield');
@FOR( PATTERN( I) | I #LE# NPATS: @WRITE( @FORMAT( I, '6.6G')));
@WRITE( @NEWLINE( 1));
@WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
@FOR( FG( F):
@WRITE((FW - @STRLEN( FG( F)))*' ', FG( F), ' ',
@FORMAT( DEM( F), '6.6G'), @FORMAT( YIELD( F), '6.6G'));
@FOR( FXP( F, P) | P #LE# NPATS:
@WRITE( @IF( NBR( F, P) #GT# 0,
@FORMAT( NBR( F, P), "6.6G"), ' .')));
@WRITE( @NEWLINE( 1))
);
@WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
@WRITE( 2*FW*' ', ' Usage:');
@WRITEFOR( PATTERN( P) | P#LE# NPATS: @FORMAT( X( P), '6.6G'));
@WRITE( @NEWLINE( 1));
ENDCALC
END
|