For our example, we will be cutting 45 foot wide rolls of paper into smaller rolls of widths: 34, 24, 15, 10 and 18.  We use Lingo’s programming capability to iteratively solve the master and subproblem until no further beneficial cutting patterns remain to be appended to the master problem.

MODEL:

! Uses Lingo’s programming capability to do

 on-the-fly column generation for a

 cutting-stock problem;

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:

 ! Send unwanted output to log file;

 @DIVERT( 'LINGO.LOG');

 

 ! Set parameters;

 @SET( 'DEFAULT');

 @SET( 'TERSEO', 1);

 @SET( 'STAWIN', 0);

 

 ! 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 = -BIGM;   ! Clearly attractive initially;

 @WHILE( RC #LT# 0 #AND# NPATS #LT# MXPATS:

   ! Solve for current best pattern runs;

   @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;

   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);

 

 ! Redirect output back to terminal;

 @DIVERT();

ENDCALC

END

Model: LOOPCUT