Re: [Help-glpk] Example for column generation

[vijay patil]

Marc,

I assume you want to use dual values of master LP problem/model, to generate new "best" column which can be added to the model. 

Please search on Internet for "cutting stock problem". It will explain need of column generation and how to use dual values to generate columns.

I just tried to write simple program (using GLPK 4.18) which uses column generation technique, to solve cutting stock problem.  Please see attached code. Its not complete (final solution is not integer).  I have NOT tested it much, so there might be many bugs. Hope it gives you some idea of column generation. Later I might write improved versions.

Thanks

On 6/27/07, Marc Goetschalckx <address@hidden> wrote:

I solving a problem with column generation.  I have solved the root
problem and now need to add columns to this existing problem and using
the current basis.  Is there an example that illustrates the mechanics
of column generation?  Thanks
Marc Goetschalckx


_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk

-- 
Vijay Patil

cutstock.c
Description: Text document