Cutting Stock Problem Example

On sci.op-research the following message was posted:

> There is a worked example of how to solve a basic Cutting Stock Problem at
> http://docs.google.com/View?docid=dfkkh8qj_64rrpz86db
> It uses simple methods, and the open source program lp_solve. Briefly,
> the solution shown is:
>
> * create a list of cut combinations (not permutations - there would be
> too many of those to work with in most cases)
>
> * from this list, generate a set of linear programming (simplex) expressions,
> and output them to a file
>
> * this file becomes the input to lp_solve, which calculates an optimal solution
>
> * most of the cut combinations in the solution will have a score of zero.
> For those that have a score greater than zero, look them up on the list
> created in step 1

A clever way to solve these problems is using a Delayed Column Generation approach. Such a model is not too difficult to code in GAMS. See http://www.amsterdamoptimization.com/pdf/colgen.pdf. A nice write up on the cutting stock problem is available from http://en.wikipedia.org/wiki/Cutting_stock_problem.

The only change to the model to solve this problem was to update the data to reflect this problem (see below). The complete model is here.