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