Cut stock problem multiple rolls

[lucaslukinha]

Hello! Your project really helped me with column generation and the cutting stock problem with CPLEX. Can you guide me with what should I modify to allow multiple rolls with different widths? Thank you!

[pcbouman-eur]

Hi Lucas, this is mostly a matter of how you model the approach. The modelling itself is kind of out of scope for this example project. You probably need to make sure that the pricing problem becomes aware of the different types of rolls, as the master problem only cares about having valid cutting patterns.

[lucaslukinha]

I know about that, but I'm struggling to get it right. I didn't find any material with a modelling for cut stock with column generation and N rolls, so I don't know what to do with initial solution, pricing problem, duals, etc.

[pcbouman-eur]

It sounds a bit like a homework problem, and I can not really help you with that. The number of rolls is actually what is decided by your decision variables that are associated with your columns. If you have different kinds of rolls, that probably means you need to have different kinds of columns.
If you struggle modelling your problem directly, you could try to write down the problem as a quadratic program where you multiply the decisions variables for how many rolls to use with decision variables that determine what goes in the rolls. Then you can try to do something similar to Dantzig-Wolfe decomposition to push the "what-goes-in-the-rolls" variables into your pricing problem, in such a way that both the Master and Pricing problem become linear. But I'm not sure if that will make your life a lot easier.