Thursday, May 15, 2008

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
> 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 A nice write up on the cutting stock problem is available from

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.