LP - How to model binary variable that indicates a switch

I have the following question / concern. I have a modeling problem with the decision variable $$d_{ptm}$$ which indicates whether product $$p$$ was serviced by machine $$m$$ in period $$t$$. It takes the value 1 if so, and 0 otherwise. A product can be serviced by different machine in different periods. In addition, a product may not be serviced for two days and then again, possibly by a different machine. I now want to introduce a binary variable $$\rho$$ that indicates such a switch in machines a product was serviced by. It should take the value = 1 if there was a machine switch from the last time a product was serviced till the current period. How can I model this? The constraints should not only create a lower bound, but also an upper bound. It should not be compared to the previous period, but to the time $$t$$ when the last time a product was serviced by a machine. In another thread I already found the solution for a switch compared to previous day, but I would like to have it compared to the last day with a machining. My idea would be to somehow remember the status, but I have no idea how to do it.

My constraints so far (adopted from post mentioned above): $$d_{ptm}-d_{p(t+1)m}\le\rho_{p(t+1)} \\ d_{ptm}+d_{p(t+1)m}+\rho_{p(t+1)}\le 2$$

EDIT: Model shift change using $$w_{ptm}$$: \begin{align} &d_{ptm}+\sum_{j \neq m} w_{ptj}\le \rho_{pt}+1~&\forall p \in P, m\in M, t\in\{2,\ldots,T\}\\ &w_{ptm}+d_{ptm}+\rho_{pt}\le 2~&\forall p \in P, m\in M, t\in\{2,\ldots,T\} \end{align} Definition of $$w_{ptm}$$: \begin{align} &w_{ptm}\ge d_{p(t-1)m}~&\forall p\in P, m\in M, t\in\{2,\ldots,T\} \\ &w_{ptm}\ge w_{p(t-1)m}-\sum_{j \in M\setminus\left\{ m \right\}} d_{p(t-1)j} ~&\forall p\in P,m\in M, t\in\{2,\ldots,T\}\\ &\sum_m w_{ptm} = 1 ~&\forall p\in P, t\in \{2,\ldots,T\} \end{align}

• Hint: introduce a binary decision variable $s_{ptm}$ that indicates whether the last servicing of product $p$ in periods prior to $t$ was on machine $m$. Jun 11, 2023 at 17:52
• @RobPratt I added my approach but it is not linear. Jun 12, 2023 at 12:05
• I changed it. Sorry my bad, I used the wrong indices Jun 13, 2023 at 16:22
• Thanks, i updated my constraints. Why $\sum_t$ and not $\sum_m$? Doesn't it make more sense that there is only one last "service" over all machines? Whenever i use $\sum_t$ the Gurobi model gets infeasible, while using $\sum_m$ it generates a solution. But using $\sum_m$ still comes with the problem, that some of the $w$'s are 1 even though they are actually 0 leading the model to indicate more changes than there actually are. How to enforce $w_{ptm}=0$ whenever $d_{p,t-1,m}=0$? Jun 13, 2023 at 17:50
• Yes, sorry. It should be $\sum_m$ for each $p$ and $t$, like in my answer. Your next-to-last constraint mixes $\sum_m$ and $\forall m$; compare to the last constraint in my answer. Jun 13, 2023 at 18:26

Following my hint, introduce a binary decision variable $$s_{ptm}$$ that indicates whether the last servicing of product $$p$$ in periods prior to $$t$$ was on machine $$m$$. You want to enforce $$\rho_{ptm} \iff \lnot s_{ptm} \land d_{ptm},$$ equivalently, $$\rho_{ptm} = (1-s_{ptm}) d_{ptm},$$ which can be linearized in the usual way: \begin{align} \rho_{ptm} &\le 1-s_{ptm} &&\text{for all p,t,m} \\ \rho_{ptm} &\le d_{ptm} &&\text{for all p,t,m} \\ \rho_{ptm} &\ge (1-s_{ptm}) + d_{ptm} - 1 &&\text{for all p,t,m} \end{align}
It remains to enforce the definition of $$s_{ptm}$$. Let binary decision variable $$x_{pt}$$ indicate whether no service is performed for product $$p$$ at time $$t$$: $$\sum_m d_{ptm} + x_{pt} = 1 \quad \text{for all p,t}$$ You want to enforce $$s_{p,t+1,m} \iff d_{ptm} \lor (s_{ptm} \land x_{pt}),$$ equivalently, $$s_{p,t+1,m} = d_{ptm} + s_{ptm} x_{pt},$$ which can be linearized as follows: \begin{align} s_{p,t+1,m} &= d_{ptm} + y_{ptm} &&\text{for all p,t\not=T,m} \\ y_{ptm} &\le s_{ptm} &&\text{for all p,t,m} \\ y_{ptm} &\le x_{pt} &&\text{for all p,t,m} \\ y_{ptm} &\ge s_{ptm} + x_{pt} - 1 &&\text{for all p,t,m} \end{align}
It is worth noting that network modeling provides a powerful framework for multiperiod situations like this where you want to capture pairwise interactions between decisions. Let node $$(p,t,m)$$ represent servicing of product $$p$$ at time $$t$$ on machine $$m$$, and let a directed arc from $$(p,t,m)$$ to $$(p,t',m')$$ represent that product $$p$$ was serviced at times $$t$$ and $$t'$$ and no other times between $$t$$ and $$t'$$. Now a servicing schedule for product $$p$$ corresponds to a path in the network. Your $$\rho$$ variable is then a sum of arc variables for which $$m\not= m'$$.
• Thank you very much. That was exactly what I was looking for. One last question. How do I force $\rho_{pt}=0$, like it was done in the mentioned thread? Jun 12, 2023 at 15:09
• Glad to help. I made some corrections just now because my $\rho$ variable actually depended on $(p,t,m)$, not just $(p,t)$. The two $\rho_{ptm} \le$ constraints force $\rho_{ptm}=0$ when there is no switch to machine $m$. The sum $\sum_m \rho_{ptm}$, which will take a value in $\{0,1\}$, represents whether there was a switch to some machine or not. Jun 12, 2023 at 15:28
• Thank you. Would the same formulation be true if only $\rho_{p,t}$ were valid, that is, if only to show that the machine is different in day $t$. And $p'$ could be replaced with any character, correct? Jun 12, 2023 at 15:43
• No, if you omit the $m$ index, the $\rho \ge$ constraint is correct but not the two $\rho \le$ constraints. Yes, $p'$ is just a dummy index, and you could instead use $q$, for example. Jun 12, 2023 at 15:57
• Is it then possible to formulate this relation also for $\rho_{pt}$? Or can I formulate $\sum_{m}^{}\rho_{ptm}=\gamma_{pt}$ and then $\gamma_{pt}$ is my switch indicator. Or would that not work because then the sum might not be either 0 or 1. So my primary concern is to find a binary variable that is only valid for $p$ and $t$, so to speak. If you could formulate this for me again, I would be infinitely grateful. Jun 12, 2023 at 16:07