This can be implemented as follows. Our notation is again:
Then the master problem in the column generation approach can look like: 
where we have the following constants: 
The subproblem can be formulated as: 
The initialization of the algorithm needs a little bit more sophistication than I had before, to make sure a feasible initial solution is created. Alternatively it may be more convenient to make the master elastic with respect to the availability constraint, so that it is easier to construct a feasible solution. An example solution can look like:
Interesting models. thanks for sharing. Another followup:
ReplyDeletewhat if i have a limit P on the number of patterns (p) used?
I think that would require some thought. Putting counting active patterns in the master would make it a MIP.
ReplyDeleteHi Erwin, this is very good! Thanks so much for sharing! btw, I'm trying to implement this with glpk and regarding the upper indexes k(p), I'm not sure how to implement it. Is this a function that only helps you know which pattern and variables belongs to which raw material? or is it somehow implemented as a bigger matrix?
ReplyDeleteThanks, Dan
k(p) is a mapping from a given cutting pattern p to a raw material width. Could just be an extra array indexed by a pattern number but other data structures are also possible,
ReplyDeleteGot it. Thanks Erwin!
ReplyDelete