# Network formulation based side constraints for a workforce scheduling problem

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?

• You might consider omitting “long” arcs that would schedule a worker for two consecutive shifts that are far apart in time. Apr 21 at 0:18
• But would it not result in less flexibility and a suboptimal solution?
– SDC
Apr 21 at 4:18
• 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. Apr 21 at 4:23
• 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.
– prubin
Apr 21 at 15:35
• @prubin The arcs join shifts from different days. Apr 21 at 15:38