I have the following constraints for my roster optimisation problem: \begin{align} &(1-r_{i,t})\le \sum_{j=t-\chi}^{t-1}sc_{i,j}\quad &\forall i\in I, t\in \{1+\chi,\ldots,T\} \end{align} \begin{align} &M\cdot (1-r_{i,t})\ge \sum_{j=t-\chi}^{t-1}sc_{i,j}\quad &\forall i\in I, t\in \{1+\chi,\dots,T\} \end{align} \begin{align} &r_{i,t}=0\quad &\forall i\in I, t\in \{1,\ldots,\chi\} \end{align} It is intended to ensure that the binary variable $r_{it}$ assumes the value one if the binary variable $sc_{i,t}$ was always zero in the previous $\chi$ days (there was no shift change in the last $\chi$ days). Otherwise, $r_{i,t}=0$ should apply if there was such a shift change. The variable $r_{i,t}$ is then used in the model to enable work performance to be restored. Now to my question / problem.

  1. Is it possible to improve / summarise the three constraints?
  2. Main problem: The variable $r_{i,t}$ can also take the value of 1 in this modelling if, for example, there was no change on the first three days ($t=1-3$). However, I actually want to model that this possible assignment of $r_{i,t}$ is only possible from the first shift change in the planning horizon. In other words, only once $sc_{i,t}=1$ has applied.

Example 1: $\chi=2$ applies. $sc_{i,t}=[0,0,0,1,1,0,0,0,0]$, then it currently follows that$r_{i,t}= [0,0,1,1,0,0,0,0,1]$.

Example 2 (as it should be): $\chi=2$ applies. $sc_{i,t}=[0,0,0,0,1,1,0,0,0]$, then it should follow: $r_{i,t}= [0,0,0,0,0,0,0,0,1]$.


1 Answer 1

  1. You are enforcing: \begin{align} \lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1} \implies r_t &\equiv \lnot (\lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1}) \lor r_t \\ &\equiv (sc_{t-\chi}\lor\dots\lor sc_{t-1}) \lor r_t \\ &\equiv sc_{t-\chi}+\dots+sc_{t-1}+r_t \ge 1 \\ &\equiv 1-r_t \le sc_{t-\chi}+\dots+sc_{t-1} \end{align} which is your first constraint.

You are also enforcing: \begin{align} sc_{t-\chi}\lor\dots\lor sc_{t-1} \implies \lnot r_t &\equiv \lnot ( sc_{t-\chi}\lor\dots\lor sc_{t-1}) \lor \lnot r_t \\ &\equiv (\lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1}) \lor \lnot r_t \\ &\equiv \land_{k=t-\chi}^{t-1} (\lnot sc_k \lor \lnot r_t) \\ &\equiv 1-sc_{k}+1-r_t \ge 1 &&\forall k=t-\chi,\dots,t-1\\ &\equiv sc_k \le 1-r_t &&\forall k=t-\chi,\dots,t-1\\ \end{align} This is the disaggregated version of your second constraint (tighter), with $M=\chi$.

  1. If my understanding is correct (?), you want to enforce: $$ (\lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1}) \land sc_t \implies r_t $$ Using the same methodology: \begin{align} \lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1} \land sc_t \implies r_t &\equiv \lnot (\lnot sc_{t-\chi}\land\dots\land \lnot sc_{t-1} \land sc_t) \lor r_t \\ &\equiv (sc_{t-\chi}\lor\dots\lor sc_{t-1} \lor \lnot sc_t) \lor r_t \\ &\equiv sc_{t-\chi}+\dots+sc_{t-1}+(1-sc_t)+r_t \ge 1 \\ &\equiv sc_t \le sc_{t-\chi}+\dots+sc_{t-1}+r_t \end{align}

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.