Re: [Help-glpk] Simple rostering GLPK example or resources?

[glpk xypron]

Hello Harley
> Regarding the personnel assignment problem that you developed 
> [http://lists.gnu.org/archive/html/help-glpk/2009-01/msg00057.html], you 
> generate the possible shifts for each of the personnel in the following 
> statement:
> 
>    set O := setof{ v in V, s in B, d in {ri[v]..ra[v]}}( v, s, d);
> 
> and make the comment that "for large problems consider column generation 
> to create work offers". Do you mean that you would generate these 
> externally to the Mathprog model and read them in the Data section of 
> the problem using some other programming language? What are you gaining 
> by doing this? Improved execution speed or larger possible problems?
> 

I would use the GLPK API to implement a column generation approach.

The idea of column generation for the personnel assignment would be
that only those shift patterns (and the accompaning variables/columns)
will be created which are needed to improve the solution.

For an overview see
http://www.di.unipi.it/~frangio/papers/G-2007-109.pdf

The main benefit will be the possibility to solve large problems
efficiently. Column generation typically will not allow you to
prove global optimality.

For an implemented column generation algorithm with GLPK see
http://code.google.com/p/cspsol/

Best regards

Xypron
-- 
GMX DSL Doppel-Flat ab 19,99 €/mtl.! Jetzt auch mit 
gratis Notebook-Flat! http://portal.gmx.net/de/go/dsl