Employee Scheduling III: generating all shifts using the Cplex solution pool

In (1) and (2) all possible shifts for a small Employee Scheduling problem are calculated by programming. In (3) we generate new shifts one by one using MIP model as part of a Column Generation algorithm. Here I want to show a different approach to generate all possible feasible shifts with a MIP model using the Cplex solution pool. So this is a post about “modeling instead of programming”.

The model is very similar to the sub-problem in the Column Generation scheme:

binary variables    w(t) 'work at time t'    start(t) 'start of shift'    emp(e) 'select shift from employee e' ; positive variables    shiftlen  'length of shift' ; variable dummy; equations    startShift(t)    'start of shift: w(t) goes from 0 to 1'    oneShiftStart    'exactly one start of shift'    calcLen          'calculate length of shift'    oneEmployee      'pick one employee'    minLength        'observe minimum shift length'    maxLength        'observe maximum shift length'    feasibleShift(t) 'make sure shift is feasible'    dummyObj ; startShift(t)..  start(t) =g= w(t) - w(t--1); oneShiftStart..  sum(t,start(t)) =e= 1; calcLen..        shiftLen =e= sum(t, w(t)); oneEmployee..    sum(e, emp(e)) =e= 1; minLength..      shiftLen =g= sum(e, minlen(e)*emp(e)); maxLength..      shiftLen =l= sum(e, maxlen(e)*emp(e)); feasibleShift(t).. w(t) =l= sum(canwork(e,t),emp(e)); dummyObj..       dummy =e= 0; option mip=cplex; $onecho > cplex.opt SolnPoolAGap = 0.0 SolnPoolIntensity = 4 PopulateLim = 10000 SolnPoolPop = 2 solnpoolmerge solutions.gdx $offecho model solpool /all/; solpool.optfile=1; solve solpool using mip minimizing dummy;

Actually the model is quite simpler as in the CG sub-problem we needed a rather complicated objective. Here we use a dummy objective as we just need to find a feasible shift.

This model finds a shift encoded by the binary variable \(w_t\) and a corresponding employee denoted by \(emp_e \in \{0,1\}\) (the selected employee will have a value of one).

The start of a shift is easily found: we need to look for a pattern \(w_t,w_{t+1} = 0, 1\). Note that \(w_1\) for \(t=1\) is special: it may be a continuation of a shift with \(w_{24}=1\). This is the reason why in the GAMS model we use “start(t) =g= w(t) - w(t--1)” with a circular lag operator --. To make sure shifts are contiguous we only need to require that \(\sum_t start_t \le 1\) (note that \(\sum_t start_t = 0\) can not happen, so we can also write \(\sum_t start_t = 1\)).

We check if a shift is only using allowed time slots in equation feasibleShift. Here we use the set canwork(e,t) indicating which time periods are allowed or forbidden for a given employee (see (2)). We require here that if canwork=0 then the corresponding \(w_t=0\).

The Cplex solution pool (4) allows us to find all feasible integer solutions for a MIP very fast. This technology is used here to find all feasible shifts and indeed we find:

We see we find the same 1295 shifts, although in a different order (the order is not important for our purposes).

Now we have found this complete collection of feasible shifts, we can solve our scheduling model:

\[\begin{align}\min\>&\sum_s c_s x_s\\        &\sum_{s|E(e,s)} x_s \le 1 \>\forall e\\        &\sum_{s|S(s,t)} x_s \ge R_t \> \forall t\\         &x_s \in\{0,1\}\end{align}\]

With this approach we just use one MIP solve to find all feasible shifts and a second MIP solve to find the optimal schedule.

References

1. Loren Shure, Generating an Optimal Employee Work Schedule Using Integer Linear Programming, January 6, 2016, http://blogs.mathworks.com/loren/2016/01/06/generating-an-optimal-employee-work-schedule-using-integer-linear-programming/ describes the problem with a Matlab implementation.
2. Employee Scheduling I : Matlab vs GAMS, http://yetanothermathprogrammingconsultant.blogspot.com/2017/01/employee-scheduling-i-matlab-vs-gams.html has a GAMS version of the model in (1).
3. Employee Scheduling II : Column Generation, http://yetanothermathprogrammingconsultant.blogspot.com/2017/01/employee-scheduling-ii-column-generation.html
4. IBM, What is the solution pool?, http://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/soln_pool/02_soln_pool_defn.html
5. Employee Scheduling IV: direct optimization, http://yetanothermathprogrammingconsultant.blogspot.com/2017/03/employee-scheduling-iv-direct.html