Generalize working days constraints

Question

I have the following constraints. The first ensures that in my shift plan there are always exactly two days off between blocks of working days and only then does the next block begin.

It reads as follows.
$T$ is the day index and $y_{it}$ indicates whether a person $i$ works on day $t$ ($y_{i,t}=1$) or not ($y_{i,t}=0$).

\begin{align} 1 \le y_{i,t-1} + y_{i,t+1} \le 1 + y_{i,t}~~~~\forall i\in I,t\in \{2,\ldots,\mid T\mid -1\} \end{align}

How can I generalise this constraint so that it not only applies to two days? For example, that must always be at least three free days in a row. It should be possible to control the number arbitrarily via the parameter $Sec$.

The second ones go as follows: \begin{align} \ &\sum_{t=1}^7y_{i,t} \geq 5 \forall i \in I\\ \ &\sum_{t=8}^{14}y_{i,t} \geq 5\forall i \in I \end{align}

They are to ensure that in the period from $t=1-7$ and $t=8-14$ the sum of $y_{i,t}$ is at least $5$. How can I combine these two constraints and also generalise them. So that it is not only for $T=14$, but also for all other multiples of $7$, for example?

Answer 1

I will drop index $i$ in what follows.

To enforce at least $2$ free days in a row, you need to forbid patterns with 101, which translates in CNF as: \begin{align} \neg (y_{t-1}\wedge \neg y_{t}\wedge y_{t+1}) &\equiv \neg y_{t-1} \vee y_{t} \vee \neg y_{t+1} \\ &\equiv (1-y_{t-1})+y_{t}+(1-y_{t+1}) \ge 1 \\ &\equiv 1+y_{t} \ge y_{t-1} +y_{t+1} \end{align} With $y_{t-1}+y_{t+1}\ge 1$, you are also enforcing $\neg y_{t-1} \implies y_{t+1}$ which forbids you from having more than $2$ free days in row (patterns 000). So your constraints are correct. Note however that this constraint also forbids patterns 010, which may be overly restrictive (?). You may want to consider instead: $$ y_{t-1} \le y_t + y_{t+2} $$ in order to enforce $y_{t-1}\wedge \neg y_t \implies y_{t+2}$.

Similarly, you can enforce at least $3$ free days in a row by forbidding patterns with 1001, which translates in CNF as: \begin{align} \neg (y_{t-1}\wedge \neg y_{t}\wedge \neg y_{t+1} \wedge y_{t+2}) &\equiv \neg y_{t-1} \vee y_{t} \vee y_{t+1} \vee \neg y_{t+2}\\ &\equiv (1-y_{t-1})+y_{t}+y_{t+1}+(1-y_{t+2}) \ge 1 \\ &\equiv 1+y_{t}+y_{t+1} \ge y_{t-1} +y_{t+2} \end{align}

And to forbid more than $3$ days in a row, you need to enforce $y_{t-1}\wedge \neg y_t \implies y_{t+3}$ with:

$$ y_{t-1} \le y_t + y_{t+3} $$

More generally, to have at least $n$ free days in a row, you can enforce: $$ y_{t-1} \wedge \neg y_{t} \implies \neg y_k \quad \forall k=t+1,...,t+n-1 $$ with: $$ \begin{align} \neg (y_{t-1}\wedge \neg y_{t})\vee \neg y_k &\equiv \neg y_{t-1} \vee y_{t} \vee \neg y_{k} \\ &\equiv (1-y_{t-1})+y_{t}+(1-y_{k}) \ge 1 \\ &\equiv 1+y_{t}\ge y_{t-1} +y_{k} \quad \quad \quad \quad \quad \quad \quad \forall k=t+1,...,t+n-1 \end{align} $$

And to forbid more than $n$ days in a row, you need to enforce $y_{t-1}\wedge \neg y_t \implies y_{t+n}$ with:

$$ y_{t-1} \le y_t + y_{t+n} $$

For the second part of your question, you can simply write $$ \sum_{t=k}^{k+6}y_k \ge 5 \quad \forall u=0,1,2,... \quad \forall k=7u+1 $$

---

Some comments:

• There is an excellent post by @ErwinKalvelagen on this topic here.
• See also the very similar question answered by @RobPratt here.
• Since you want shifts which are quite well structured, it might be interesting to generate them beforehand and to select the best ones with a set covering formulation. A similar example is given here.

Answer 2

Have you also considered an alternate formulation where you give all possible blocks as decision variables? So, instead of working day making the model choose which working blocks should be used? This representation has the disadvantage of more variables, but it simplifies the constraints significantly. This formulation works better in certain cases. In addition, you can reduce variables by only supplying a "judicious" set of block decision variables to the model.