> There is a worked example of how to solve a basic Cutting Stock Problem at
> 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
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.
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.