One dimensional cutting stock problem — An Integer Programming approach

Consider the following case.

Demand length (Lᵢ) in meter   Demand Numbers (bᵢ)  
 9                             511                  
 8                             301                  
 7                             263                  
 6                             383

We have to find the optimum pattern in which we can cut the entire demand from a large number of bars (with length 20 meters, assume).

The problem is like this,

Simpy, generating optimum cutting pattern.

How to solve it?

Take

as the number of bars that are cut using the pattern j. Assume, excess material cut shall also be treated as waste. This results, minimizing the waste becomes minimizing a total number of cuts.

So the objective function shall be written as,

Subject to the condition

Equation number 1

Where,

is the number of bars of length Lᵢ that are present in pattern number j and

is the number of bars of length Lᵢ that are required to satisfy the demand.

Since

is a positive integer, this problem shall be treated as Integer Programming Problem (IP). To solve this, let us handle this problem as Linear Programming Problem (LP). So in order to solve using LP, we know that LP can give fractional solutions, but here in this problem, we have an Integer constraint. So let us see how to map IP from LP.

Assume that, we know the optimum pattern solution for LP.

Obviously, we can make a pattern by mathematical guess so that the demanded length can satisfy the stock length.

So the patterns are,

Only 9m bar can be cut and 255.5 bars are needed for it

Only 8m bar can be cut and 87.625 bars are needed for it

7m and 6m bars can be cut and 131.5 bars are needed for it

8m and 6m bars can be cut and 125.75 bars are needed for it

So in total, we may need 600.375 bars to satisfy our demands. This is fully based on LP. And clearly, we can say that the upper rounding off the value of 600.375 will be the lower bound of IP in this problem. That is, if we solve using IP, the optimum should be 601 or more.

Let us consider the following three key methods to ensure the optimum IP mapped from LP.

The optimum solution from LP is always lesser or equal to that from IP and here, the Optimum from IP is 601

We can verify that the pattern satisfies the demand as follows.

9m   2x255.5            511  Satisfied
8m   2x87.625)+125.75   301  Satisfied
7m   2x131.5            263  Satisfied
6m   2x125.75)+131.5    383  Satisfied

2. Finding the feasible using an upper integer value

In this method, we have to round off the requirement obtained from LP generated pattern to the upper value.

Pattern 1   255.5    256  
Pattern 2   87.625   88   
Pattern 3   131.5    132  
Pattern 4   125.75   126

Now we have a total of 602 bars. So we found the upper bound value for the optimum in IP.

The worse case in the upper bound must not exceed k where k is the number of demand lengths. Here in this example, k=4.

3. Finding the feasible using a lower integer value.

Patterns    Requirement  Rounded off    Demand length   Shortage 
 
Pattern 1   255.5         255           9m              1         
Pattern 2   87.625        87            8m              2         
Pattern 3   131.5         131           7m              1         
Pattern 4   125.75        125           6m              2

Now we have a total of 598. We have 3 bar shortage from the lower bound. Now we have to try to satisfy the shortage and if it satisfied within 3 bars, 601 would be the feasible solution for the problem. By mathematical guessing, we can make patterns to satisfy the shortages.

1 of 9m, 2 of 8m, 1 of 7m, and 2 of 6m are achieved

We can go for several patterns to satisfy the shortage. Now we have the feasible solution with 598+3=601 bars. Since the lower bound of IP is 601, the optimum for IP is gained, 601.

Now, let us try to solve LP optimum to get IP optimum.

Choose the base pattern arbitrarily. So the Basic matrix (B) with base patterns shall be given by

Requirement (R) for B is

and we need 665.16 bars in total.

Now the question is, is it the optimum that we are looking for?

Calculate the values of

for all nonbasic patterns. If the values are positive, the current basic feasible solution is the optimal solution. If there are one or more negative values, choose the variable corresponding to which the value of

is least (most negative) as this is likely to decrease the wastage. Here,

is the coefficient of the variables in the objective function. While

and

is the coefficients of the current basic variables in the objective function.

Consider the formulation, the problem is

subject to the constraint

In this example, n=4

What is the dual of the problem?

Let

as the dual variable. There are 4 dual in this problem each associated with the 4 constraints. So the dual is a maximization problem. Therefore the problem is,

such that

the upper bound is 1 because

has the objective function coefficient 1. Also the dual is unrestricted in sign as all the primal constraints are equation.

As we saw earlier, the entering pattern must have

then such a pattern

can enter the base.

How to get the dual y?

Let the new pattern

as

such that

and

where

It belongs to an integer because all the pattern values must be an Integer value.

then that pattern can enter the base B.

Since the problem is in IP ( as the constraint Integer presents), still the problem is inapproachable as the constraint deals with strictly greater than 1. Whatever the LP or IP, the problem is reachable only when the constraints deal with less than or equal to or greater than or equal to.

Therefore we rearrange the optimization as follows.

The problem now is,

subject to the condition

and

It belongs to an integer because all the pattern values must be an Integer value.

And now it became a Knapsack problem with a single constraint.

By relaxing the Integer constraint, IP becomes LP and single constraint LP has a simple solution that variables which has the largest ratio of objective function to constraint will be in the solution.

By arranging these ratios in decreasing order, name them with

So now,

subjected to,

By multiplying the LCM along with the function,

subjected to,

Remove the integer constraint,

Let us construct the tree now.

Integer feasible solution for IP reached with Z=8.

Now the entering pattern is,

Already we have 4 patterns in the Base matrix. Now we have to find out the leaving pattern.

From the earliest requirement,

This results,

By

And this belongs to the third pattern in B, hence it leaves. So now the base matrix

Now the requirement

as

In other words, the gain is 43.83. (ie; 655.16–621.33=43.83).

Similarly, when you are carrying out this method until the problem gives no entering pattern. In this problem, the final cutting pattern, the base matrix is,

with the requirement

And that is the optimum solution for this problem.

The rest of the methods will be updated if you need more assistance to solve this problem or in understanding the problem.