Re: [Help-glpk] Simple Cutting Stock Problem Solver Using GLPK

[Andrew Makhorin]

Hi Vijay,

> I wrote a program to solve cutting stock problem. Program is written
> in C++ and uses GLPK C API.  Customized branch & bound (BB) algorithm
> is used. Each node of BB tree is a LP. Each node LP is solved using
> column generation (CG). Very simple branching on fractional variable
> is used to obtain integer solution. BB tree is traversed using breadth
> first search (BFS) strategy.

> Hopefully program will be useful to anyone interested in learning GLPK
> C API and understand column generation technique. In case you want to
> have a look at the source code, following web-page has more details,
> including source code:

> http://code.google.com/p/cspsol/

> I have not tested the program extensively. It is likely that program
> has some flaw or incorrect use of GLPK C API. Your feedback/comments
> are welcome.

The code is nice. (Sometimes C++ is more expressive than C. :)

The only question: why do you assign penalties to slack variables
initially introduced in the master lp? In your code each slack variable
has a unity column, which itself might be considered as a pattern, so
there would be no difference between slack and pattern variables.


Andrew Makhorin