First, we have the sets section:

SETS:

 PATTERN: COST, X;

 FG: WIDTH, DEM, PRICE, Y, YIELD;

 FXP( FG, PATTERN): NBR;

ENDSETS

The PATTERN set is used to represent the cutting patterns we will be generating.  Each pattern has a cost, which, with one exception (discussed below), will be 1, i.e., each pattern uses 1 raw material piece.  We also assigned an attribute called X to the patterns set. X( p) will be used to store the number of times each pattern p is to be cut and is one of the decision variables.

The FG set is used to represent the set of finished goods.  As input, each finished good has a width and customer demand.  The PRICE attribute will be used to store the dual prices on the finished goods.  These prices will be updated each time we solve the master problem. Y will be an integer, decision variable that we will use in the knapsack subproblem to represent the number of pieces of each finished good to use in the next generated pattern. YIELD will be used to store the number of pieces of each finished good that gets produced.

The derived set, FXP, is derived on the finished goods and patterns sets.  The attribute NBR( i, j) will store the number of finished goods I contained in pattern j.

Next, we have the data section

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

We initialize the pattern set to have 20 members.  This will only allow for generation of up to 20 patterns; however, this should be more that adequate for this small example.

After inputting the raw material width of 45, we input the set of five finished goods and their widths.   After that, we input the demands for the finished goods.  Finally, we input a parameter called BIGM, the purpose of which is discussed below.

Next, we have our first submodel:

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

This is the master problem we’ve been mentioning.  The objective states that we wish to minimize the total cost of all the patterns used.  The constraint says that we must meet, or exceed, demand for all the finished goods.

The next submodel:

SUBMODEL INTEGER_REQ:

 @FOR( PATTERN: @GIN( X));

ENDSUBMODEL

will be used in conjunction with the master problem to force the variables to take on integer values.  Given that it’s not possible to cut a fractional number of a particular pattern, for our final solution we need the X variables to be integer valued.

Our final submodel:

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

is the pattern-generation subproblem we’ve mentioned.  This is a knapsack problem that finds the best pattern that can be cut given the dual prices on the finished goods.  Recall that we get the dual prices on the finished goods from the demand constraints in the master problem.

We then enter the calc section, which contains the programming logic to coordinate the iterative algorithm we’ve chosen.  As with the previous Markowitz model, the start of the calc section is devoted to diverting output to a file and setting of parameters.  You may refer to the previous Markowitz model for a discussion of why these steps are being performed.

One of the features of this model most likely to change in the future would be the maximum number of patterns to generate.  It’s probably not wise to assume that this number will always be fixed at 20 patterns.  For this reason, we use the @SIZE function to get the current number of allowed patterns:

 ! Max number of patterns we'll allow;

 MXPATS = @SIZE( PATTERN);

Next, we construct what we refer to as a "super pattern":

 ! Make first pattern an expensive super pattern;

 COST( 1) = BIGM;

 @FOR( FG( I): NBR( I, 1) = 1);

The supper pattern is a device to jumpstart our algorithm by guaranteeing that the model will be feasible from the start.  We need the model to always be feasible in order to obtain a valid set of dual prices to feed into the pattern generation submodel.  The super pattern is an artificial pattern that can create one piece of each finished good.  In real life, such a pattern would not be possible because we can’t physically fit one of each finished good on a single raw material piece.  Given that the super pattern is not physically possible, we assign it a high cost, BIGM, so it will not be used in the final solution

Recall that NBR( i, j) represents the number of finished good i in pattern j.  So, for our super pattern, we use a for loop over all the finished goods i, setting NBR( i, 1) to 1 for each of the finished goods.  The second index of NBR is set at 1 given that the super pattern is the first pattern generated.

Next, the main loop that will alternate between solving the master and subproblem until an optimal solution is found:

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

 );

First, we set the pattern count, NPATS, to 1 for the one pattern already generated, i.e., the super pattern.  We will increment NPATS each time we generate a new pattern in our main loop.

Next, is the main @WHILE loop, which will execute until its condition evaluates false.  We test two things in the condition.

First, we see if the marginal impact of the current pattern, RC, is negative and will, therefore, reduce the current cost.  If the current pattern will reduce our cost, then this implies that we should continue looping and generating patterns, because subsequent patterns may also be helpful.  Once the marginal benefit of the current best pattern goes to zero, generating subsequent patterns will be of no benefit; if the current best pattern can’t help, subsequent patterns of less value will also be of no help.  In which case, we should exit our loop.

The second condition on the loop tests to see if we’ve generated the maximum allowed number of patterns that we’ve allocated space for.  If so, we must exit the loop.

Once in the loop, our first step is to invoke the @SOLVE command to solve the master problem.  We then use an @FOR loop to pass the dual values on the finished goods to the pattern generation subproblem.  We then solve the pattern generation subproblem and compute RC, the marginal rate of decrease in the main objective using the new pattern.  Finally, at the end of the loop we append the new generated pattern to the master program for the next pass through the loop.

Once we can no longer find a cutting pattern that will further reduce our costs, we exit the loop and solve the master problem one last time:

 ! Finally solve Master as an IP;

 @SOLVE( MASTER_PROB, INTEGER_REQ);

The one difference is that we now include the integer restrictions on the pattern usage array, X.  As mentioned, cutting fractional quantities of a pattern is not physically possible, so we want our final solution to be integral.

The version of this model in the samples folder has an additional calc section to prepare a tabular report on the cutting patterns and their usage.  We will not go into the details of this table-generating code in this discussion.  However, if you run the model, you should receive the following report:

Total raws used:    985

 

Total feet yield:   43121

Total feet used:    44325

 

Percent waste:      2.7%

 

                   Pattern:

FG  Demand Yield   1   2   3   4   5   6   7   8   9

=====================================================

F34    350   350    1   .   .   .   1   .   .   .   .

F24    100   100    1   .   .   .   .   1   .   .   1

F15    800   801    1   .   3   .   .   .   1   1   .

F10   1001  1002    1   4   .   .   1   2   1   3   .

F18    377   377    1   .   .   2   .   .   1   .   1

=====================================================

           Usage:  0   0 133   0 350   0 277 125 100

A total of 985 raw materials were used, with only 2.7% of the raw material input lost to trim waste.  Note that only 9 patterns were needed to solve the model.  Also note that Pattern 1, the super pattern, is not used in the final solution as per our design.