Saturday, May 31, 2008

More cutting stock

Follow up on http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/cutting-stock-problem-example.html.

>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

See also: http://people.sabanciuniv.edu/ertekg/papers/2006/alp_et_al_ims2006.pdf.
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 Total

width1 1 2 100
width2 1 2
width3 1 2
width4 2 1 2 250
width5 2 2
width6 1 2
width7 1 2
width8 1 2
Count 75 1 2 2 2 49 131

2 comments:

  1. >Hi Erwin,
    >
    >You are right - my pattern generator missed some possible patterns. Will post corrected solution on lp_solve list later.
    >

    ReplyDelete
  2. Hi Erwin,
    I was able to reproduce by relaxing the constraints and then tightening them. If I start directly with equality constraints I always get stuck at the beginning of the iterations with almost no patterns generated and a bad sub-optimal solution. Could my initialization be causing this? Would you mind sharing some tips on that? Thanks, I really appreciate!

    ReplyDelete