• Gurobi Staff
Hi Zeyang,

The real issue is that the constraints do not accurately model the requirements such as maximum and minimum limits on the number of consecutive working days for each employee.

To ensure the accurate implementation of the constraints, it is recommended to first represent each mathematically.

• $$x_{eij}$$ equals 1 if employee $$e$$ is assigned to shift $$i$$ on day $$j$$ and 0, otherwise
• $$y_{ej}$$ equals 1 if employee $$e$$ is working on day $$j$$ and 0, otherwise [this is a new variable to use instead of $$b$$]
Before implementing the constraints enforcing the maximum and minimum limits on the number of consecutive working days, let us formulate the relationship between the variables $$x_{eij}$$ and $$y_{ej}$$.
• If $$\sum_i x_{eij} = 1$$  $$\Rightarrow$$  $$y_{ej} = 1$$  $$\forall e, j$$
• If $$\sum_i x_{eij} = 0$$  $$\Rightarrow$$  $$y_{ej} = 0$$   $$\forall e, j$$
Note that we already know that each employee can be assigned to at most one shift per day ($$\sum_i x_{eij} \leq 1, \forall e, j$$). The above constraints are logically equivalent to:
• If $$y_{ej} = 0$$ $$\Rightarrow$$  $$\sum_i x_{eij} = 0$$  $$\forall e, j$$
• If $$y_{ej} = 1$$ $$\Rightarrow$$ $$\sum_i x_{eij} = 1$$   $$\forall e, j$$

Since the indicator variable is binary, we can implement these two constraints using the  Model.addGenConstrIndicator() method.

Using the auxiliary variables $$y_{ej}$$, it is now easier to implement the maximum and minimum limits on the number of consecutive working days:

• Maximum Limit
• If $$y_{ej} = 1$$ $$\Rightarrow$$  $$\sum_{k \in S_j} \sum_i x_{eik} \leq \mbox{MAX}$$  $$\forall e, j$$ where $$S_j=\{k | j -\mbox{MAX} < k < j + \mbox{MAX}\}$$
• Minimum Limit
• If $$y_{ej} = 1$$ $$\Rightarrow$$  $$\sum_{k \in S_j} \sum_i x_{eik} \geq \mbox{MIN}$$  $$\forall e, j$$ where $$S_j=\{k | j -\mbox{MIN} < k < j + \mbox{MIN}\}$$

Note that the set $$S_j$$ should include all days before and after day $$j$$ because variables $$x_{eij}$$ do not represent the start working day for employee $$e$$. This was the main issue with your implementation.

See the snippet attached for the implementation of the above. The indicator constraints are implemented using the overload form. The constraints associated with the "prohibited sequences" are removed because I could not fully understand what they mean. Hopefully, you can implement them given the above changes. If not, please clarify what this set of constraints does.

I did run the snippet below using your data and the maximum and minimum limits are now enforced.

m = gp.Model("employee_scheduling")# Decision variablesx = m.addVars(EMPLOYEE, range(nS), range(nD), vtype=gp.GRB.BINARY, name="x")y = m.addVars(EMPLOYEE, range(nD), vtype=gp.GRB.BINARY, name="y")# Objective functionm.setObjective(x.sum(), sense=gp.GRB.MINIMIZE)# Constraints 1: Each employee is assigned to at most on one shift per daym.addConstrs(x.sum(e, "*", j) <= 1 for e in EMPLOYEE for j in range(nD))# Constraints 2: Demandm.addConstrs(x.sum("*", i, j) >= Dem[i][j] foriinrange(nS) forjinrange(nD))# New Constraints enforcing the relationship between x and ym.addConstrs(    ((y[e, j] == 1) >> (x.sum(e, "*", j) == 1)) for e in EMPLOYEE for j in range(nD))m.addConstrs(    ((y[e, j] == 0) >> (x.sum(e, "*", j) == 0)) for e in EMPLOYEE for j in range(nD))# Constraints 3: Maximum limit on the number of consecutive working daysm.addConstrs(   (        (y[e, sD1] == 1)        >> (            gp.quicksum(                x.sum(e, "*", j)                for j in range(max(0, sD1 - MAX + 1), min(sD1 + MAX, nD))           )           <= MAX       )   )   for sD1 in range(nD)   for e in EMPLOYEE)# Constraints 4: Minimum limit on the number of consecutive working daysm.addConstrs(    (        (y[e, sD1] == 1)        >> (           gp.quicksum(               x.sum(e, "*", j)               for j in range(max(0, sD1 - MIN + 1), min(sD1 + MIN, nD))          )          >= MIN        )    )    for sD1 in range(nD)    for e in EMPLOYEE)m.optimize()

Best regards,

Maliheh

Hello Maliheh,

Would you like to explain it, "Note that the set  should include all days before and after day j.... "? Why do I need to consider both parts, before and after the time point, , that means the width of the time window is 2*MAX instead of MAX?

• Gurobi Staff

Hi Zeyang,

Would you like to explain it, "Note that the set Sj should include all days before and after day j.... "? Why do I need to consider both parts, before and after the time point, xeij, that means the width of the time window is 2*MAX instead of MAX?

Maybe my previous explanation was not clear enough. The decision variable $$x_{eij}$$ only tells us whether employee $$e$$ is working on day $$j$$ or not. We do not know if day $$j$$ is the first working day of employee $$e$$, it is the second day, or the final day, for example. Since we do not know employee $$e$$'s first working day, we need to account for the sum of all consecutive days where day $$j$$ might be the first or the last working day of employee $$e$$. That's why the width of the time window considered here is 2*MAX and 2*MIN. Hope it is clear now.

Best regards,

Maliheh

Hello Maliheh,

Thanks for the explanation. Now I understand why the boundarys are set like this. Your solution solved all my problems.

Best regards,

Zeyang