For a workforce scheduling problem, I have formulated the "at most one shift per day" constraint as a network formulation based side constraint (with other constraints like demand coverage, budget, min/max weekly/daily hours, min rest days etc.). For each worker, there is a set of eligible shifts (meaning the worker is available and qualified). Each shift is a node in the network. The directed arcs in the network are as follows:

  1. from source node to each shift node
  2. from each shift node to the sink node
  3. from shift s1 to shift s2 if s2 is a possible shift after s1

I have linked these new arc variables to the worker-shift-assignment variables that already exist in the model. While testing this new model I noticed that the worker shift network is too dense (each shift has a very large set of other valid shifts) and edge heavy. Even for a smaller problem (about a few thousand candidate shifts and a handful of workers, the number of arc variables grows to millions), the solver (Gurobi in this case) struggles to find a solution. Is there a way to reduce the arc variables?

  • $\begingroup$ You might consider omitting “long” arcs that would schedule a worker for two consecutive shifts that are far apart in time. $\endgroup$
    – RobPratt
    Apr 21 at 0:18
  • $\begingroup$ But would it not result in less flexibility and a suboptimal solution? $\endgroup$
    – SDC
    Apr 21 at 4:18
  • $\begingroup$ Yes, if you don’t have such a restriction in the original problem, then omitting these arcs might yield a worse objective value. But this is a reasonable approach to get a good starting solution. $\endgroup$
    – RobPratt
    Apr 21 at 4:23
  • $\begingroup$ The question calls the network a formulation of an "at most one shift per day" constraint, but then you say arcs represent shifts following other shifts. There seems to be a disconnect here. $\endgroup$
    – prubin
    Apr 21 at 15:35
  • $\begingroup$ @prubin The arcs join shifts from different days. $\endgroup$
    – RobPratt
    Apr 21 at 15:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.