## Saturday, May 31, 2008

### More cutting stock

>I decided to have a go at the challenge set in this paper - hope you don't mind.
>
We receive bars of length 1200 and must cut them into the following
> [length, quantity] pairs:[100,100],[200,2],[300,2],[493,250],[590,2],
> [630,2],[780,2],[930,2]
....
>So the solution equates to:12 * [100,100,100,100,100,100,100,493]2 *
> [100,100,100,100,100,630]2 * [100,100,930]2 * [100,300,780]2 *
>[100,493,590]118 * [200,493,493]
>
>Total bars used = 138
>
>Theoretical min:
>(100*100+200*2+300*2+493*250+590*2+630*2+780*2+930*2)/1200=116.76

>
>...and, finally, the numbers of each length of bar cut:100: 12 * 7 + 2 * 5 + 2 * 2 +
>2 * 1 + 2 * 1 = 102200: 118 * 1 = 118300: 2 * 1 = 2493: 118 * 2 + 2 * 1 + 12 * 1 =
>250590: 2 * 1 = 2630: 2 * 1 = 2780: 2 * 1 = 2930: 2 * 1 = 2

I can find a better solution using the column generation model. The following input was used:

``*-----------------------------------------------------* Data*----------------------------------------------------- scalar r 'raw width' /1200/; table demanddata(i,*)           width  demand  width1    100     100  width2    200       2  width3    300       2  width4    493     250  width5    590       2  width6    630       2  width7    780       2  width8    930       2;``

The result is a solution (not proven optimal) of 131:

``----    174 PARAMETER pat  pattern usage                 p4          p5          p9         p10         p11         p15       Totalwidth1                                               1                       2         100width2                                                           1                       2width3                                               1                                   2width4           2                       1                                   2         250width5                       2                                                           2width6                                   1                                               2width7                                               1                                   2width8                                                           1                       2Count           75           1           2           2           2          49         131``