I'd like to ask your opinion about how to model a constraint. The constraint can be either linear or non linear.
CONTEXT: employee scheduling. $N$ employees can be assigned to $M$ shifts, each shift belongs to a day $D$. I created a binary variable $x_{n,m,d}$ where $x_{n,m,d} = 1$ indicates that employee $n$ is assigned to shift $m$ at day $d$ (the $d$ index is useful for other constraints).
CONSTRAINT TO MODEL: each employee prefers to work at least $K$ days in a row. (i.e. $k$ consecutive days with at least one shift per day)
What I already did is to model a variable "working_day [n,d]" that tells if the employee n has at least a shift in the day $d$.
Any idea?
Best Answer
According to your topic, you already have a binary variable $x_{n,m,t} \in \{0,1\}$ that indicates whether employee $n$ is assigned to shift $m$ at day $t$ and a binary variable $y_{n,t} \in \{0,1\}$ that indicates whether employee $n$ works at day $t$ or not. Let $T$ the total number of days.
We can solve this problem with linear constraints as follows. Introduce an additional binary variable $z_{n,t} \in \{0,1\}$ that indicates whether employee $n$ start a sequence of consecutive working days at day $t$. A sequence of working days starts at day $t$ if the employee does work at day $t$ whilst not working at day $t-1$, i.e., $y_{n,t} = 1$ and $y_{n,t-1} = 0$. Then we can introduce the constraint that a sequence of working days can only start if the following $k-1$ days are also working days.
$$ \begin{align} &z_{n,1} = y_{n,1} \>\> \text{for } && && \mbox{First working day}\\ &z_{n,t} \geq y_{n,t} - y_{n,t-1} &&\text{for } t = 2, \ldots, T && \mbox{First working day}\\ &k \cdot z_{n,t} \leq \sum_{i=0}^{k-1} y_{n,t+i} \>\> &&\text{for } t = 1, \ldots, T-k+1 && \mbox{At least $k$ consecutive working days} \end{align} $$ The first constraint enforces $z_{n,t}$ to be 1 if employee $n$ starts working at day $t$ and the second constraint enforces $z_{n,t}$ to be zero if employee does not work at least the upcoming $k$ days (including the current day).