Consecutive Shift Constraint
AnsweredHello,
I'm working through the Workforce Scheduling example (link below) in python using gurobipy-pandas and was wondering as to how one would add the constraint so that a given worker should not have more than 3 consecutive shifts?
Workforce Scheduling example: https://gurobi-optimization-gurobipy-pandas.readthedocs-hosted.com/en/latest/examples/workforce.html
Any help would be appreciated. Thank you!
-
-
Gurobi Staff
Hi Shalini,
If you have binary variables \(x_i\) where \(x_i = 1\) means that a choice is made on day \(i\) then we can impose a limit of \(n\) consecutive choices with the following constraints
\[\sum_i^{i+n} \leq n, \quad \quad \forall i\]
This prevents \(n+1\) consecutive binary variables from summing to \(n+1\).
There is some nice functionality that pandas provides which can be used with gurobipy-pandas:
As per the example you linked let's assume we have a dataframe df:
Preference assign
Worker Shift
Amy 2022-07-02 1 <gurobi.Var *Awaiting Model Update*>
2022-07-03 3 <gurobi.Var *Awaiting Model Update*>
2022-07-05 2 <gurobi.Var *Awaiting Model Update*>
2022-07-07 2 <gurobi.Var *Awaiting Model Update*>
2022-07-09 1 <gurobi.Var *Awaiting Model Update*>
... ... ...
Gu 2022-07-10 2 <gurobi.Var *Awaiting Model Update*>
2022-07-11 2 <gurobi.Var *Awaiting Model Update*>
2022-07-12 2 <gurobi.Var *Awaiting Model Update*>
2022-07-13 2 <gurobi.Var *Awaiting Model Update*>
2022-07-14 3 <gurobi.Var *Awaiting Model Update*>
[72 rows x 2 columns]>It would be nice if the following code works:
def make_consecutive_cons(df_window):
if len(df_window) == 4: # there will be less than 4 if some days in window don't have variable
m.addConstr(df_window["assign"].sum() <= 3)
df.groupby("Worker").rolling(pd.Timedelta("4 days"), on="Shift").apply(make_consecutive_cons)but unfortunately it doesn't because there are some things which aren't working in our favor:
- groupby must return a numeric value
- rolling over one level of a multi-index is not currently implemented
- non-numeric columns (eg columns of gurobi variables) are dropped when rolling and aggregating (or applying)
I suspect that this would lead to many attempts with gurobipy-pandas being a bit ugly, perhaps "hacky", but the below code is not too bad, although not very pythonic.
In order to make this work we'll convert the multi-index to columns, loop through a Groupby object to retain the worker key (for constraint naming purposes) and loop through the Rolling object to prevent the column of variables being dropped.
for worker, df_worker in df.reset_index().groupby("Worker"):
for df_window in df_worker.rolling(pd.Timedelta("4 days"), on="Shift"):
if len(df_window) == 4:
m.addConstr(
df_window["assign"].sum() <= 3,
name=f"Consecutive_shifts_{worker}_{df_window.index[-1].date()}",
)The above code doesn't make an attempt to store these constraints in a Series but you could add them to a dictionary as we loop, with a (worker, date) key, and then construct a Series from this if you wanted to.
Note that in my experience the Pandas API is relatively fragile when it comes to groupby and rolling, with frequent changes/bugs in recent years. The above code has been tested with pandas 1.5.3 but may not work with other versions.
- Riley
0 -
-
Thank you very much, Riley!
0 -
Please sign in to leave a comment.
Comments
2 comments