I have a nurse-scheduling type of problem with a time span of a year and many employees.


My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to task } t \\ 0 \text{ otherwise} \end{cases}\\w_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to any task in day } d \\ 0 \text{ otherwise} \end{cases}\\v_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is on vacation on day } d \\ 0 \text{ otherwise} \end{cases}\end{align} Hired days: $$ H_{e} = \text{last work day}-\text{first work day} $$ Employee vacations: $$ V_{e} = \left\lceil\frac{H_{e}\cdot31}{366}\right\rceil $$


  • I cannot divide the problem more in terms of time as there are some constraints and variables that need to be calculated yearly.
  • I have the following symmetry breaking constraint: $$ \sum_{t\in T}{x_{e,t}} \le \sum_{t\in T}{x_{e-1,t}}$$
  • I have divided the problem into cliques of related tasks and employees.
  • I can provide more details about my variables and constraints if needed.


Is there a better way to formulate this problem?

Maybe I could add more symmetry breaking or redundant constraints that could speed up the solving (I'm using OR-Tools).

I also feel like I should assign group of tasks instead of individual tasks, is that a good idea?


With this formulation I have around 159245 variables and 478303 constraints with 80 employees.

  • $\begingroup$ can you give us some insights how many variables and constraints you have? $\endgroup$
    – JakobS
    Commented Oct 18, 2019 at 15:19
  • 1
    $\begingroup$ Info added, but I think that I will remove this question in favor of specific questions about how I implement some of the constraints. $\endgroup$
    – Stradivari
    Commented Oct 18, 2019 at 15:25
  • $\begingroup$ Can you add a minimal working example for the code you have using or-tools? This would make it easier to give you hints what to improve. $\endgroup$
    – JakobS
    Commented Oct 18, 2019 at 19:03

1 Answer 1


There are many approaches to formulate nurse scheduling model. In practice, MIPs and some heuristics have frequently been used. AFAIK, for large scale MIPs, column generation technique can be applied.

Some useful references are:

I hope, they would be useful.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.