Skip to main content

Consecutive Shift Constraint

Answered

Comments

3 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Riley Clement
    • 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
  • Shalini Tyagi
    • Gurobi-versary
    • First Comment
    • First Question

    Thank you very much, Riley!

    0

Post is closed for comments.