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:
 

5 comments:

  1. Interesting models. thanks for sharing. Another followup:
    what if i have a limit P on the number of patterns (p) used?

    ReplyDelete
  2. I think that would require some thought. Putting counting active patterns in the master would make it a MIP.

    ReplyDelete
  3. Hi 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?
    Thanks, Dan

    ReplyDelete
  4. 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,

    ReplyDelete