$ontext

   Column generation for work force scheduling

   Erwin Kalvelagen
   erwin@amsterdamoptimization.com

   References:
       Annemieke van Dongen, "Personeelsplanning en kolomgeneratie",
          Vrije Universiteit Amsterdam, 2005

$offtext

set
   t 'periods' /t1*t48/
   s 'possible shifts' /k1*k20579/
;

parameter req(t) 'required number of employees' /
  t1  2,  t2  5,  t3  6,  t4  5,  t5  7,  t6  7,  t7  4,  t8  6,  t9  7,  t10 7
  t11 7,  t12 7,  t13 6,  t14 5,  t15 6,  t16 6,  t17 5,  t18 4,  t19 7,  t20 6
  t21 6,  t22 4,  t23 5,  t24 5,  t25 6,  t26 6,  t27 5,  t28 7,  t29 7,  t30 6
  t31 9,  t32 6,  t33 7,  t34 6,  t35 6,  t36 7,  t37 7,  t38 4,  t39 5,  t40 5
  t41 4,  t42 5,  t43 3,  t44 4,  t45 5,  t46 3,  t47 5,  t48 4 /
;

table data(s,t)
$include AllShifts.inc
;


parameters
   a(t,s)   'matrix'
   c(s)     'cost vector'
;

a(t,s)$(data(s,t)=1) = 1;
c(s) = sum(t,a(t,s));

variables
   x(s)    'shifts used'
   z       'objective variable'
;
integer variable x;

x.up(s) = sum(t, req(t));

equations
  masterobj  'cost: total number of periods worked'
  edemand(t) 'meet required manpower'
;

masterobj..  z =e= sum(s,c(s)*x(s));
edemand(t).. sum(s, a(t,s)*x(s)) =g= req(t);

model master /masterobj,edemand/;

master.optcr=0;
solve master using mip minimizing z;
display z.l,x.l;

*--------------------------------------------------------------
* reporting
*--------------------------------------------------------------


scalars
   totreq 'total required periods'
   totusd 'total allocated periods'
;

totreq = sum(t, req(t));
totusd = z.l;

display totreq, totusd;

alias(s,s3);
set curs(s3) /k1/;
scalar k;
parameter schedule(s,t);
loop(s$(x.l(s)>0.5),
   for(k=1 to round(x.l(s)),
       schedule(curs,t) = a(t,s);
       curs(s3) = curs(s3-1);
   );
);
option schedule:0;
display schedule;