Monday, July 12, 2010

Max Availability in Cutting Stock Model

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:
image
This can be implemented as follows. Our notation is again:
imageThen the master problem in the column generation approach can look like:
imagewhere we have the following constants:
imageThe subproblem can be formulated as:
image 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: