In
http://yetanothermathprogrammingconsultant.blogspot.com/2010/07/multiple-length-cutting-stock-problem.html an extension of the standard cutting stock model is discussed. A question was posed if it would be difficult to add some availability restriction to this model. I.e. example data can look like:
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.
ReplyDelete