Binary variable switch constraints

Question

I have a set of binary variables $X = \{ x_1, x_2, x_3, ... x_N \}$ which are connect and used with the rest of the model.

I want to define a set of binary variables which represents the change between the variables in $X$ with adjacency. Let this set be $Y = \{ y_1._2, y_2._3, y_3._4, ... y_{N-1}._{N} \}$.

This set $Y$ is expected to behave like this,

$$y_i._{i+1} = \begin{cases} 0 & \text{if $x_i=x_{i+1}$ } \\ 1 & \text{otherwise} \end{cases} $$

Eventually, I wish to limit the summation of these $y_i._{i+1}$ variables, but that is an easy part. Question is, how can I define $y_i._{i+1}$ variables in the OR model in terms of $X$ variables which reflects the multi-definition above?

Answer 1

You want to enforce $$ \lnot y_{i,i+1}\iff (x_i\iff x_{i+1}). $$ Rewriting in conjunctive normal form yields $$ (\lnot y_{i,i+1} \lor \lnot x_i \lor \lnot x_{i+1})\land (\lnot y_{i,i+1} \lor x_i \lor x_{i+1}) \land (y_{i,i+1} \lor \lnot x_i \lor x_{i+1}) \land (y_{i,i+1} \lor x_i \lor \lnot x_{i+1}), $$ from which we obtain linear constraints \begin{align} (1-y_{i,i+1}) +(1-x_i)+(1-x_{i+1})&\ge1\\ (1-y_{i,i+1})+x_i+x_{i+1}&\ge 1\\ y_{i,i+1} +(1-x_i)+x_{i+1}&\ge 1\\ y_{i,i+1} +x_i +(1-x_{i+1})&\ge 1 \end{align} Equivalently, \begin{align} y_{i,i+1}+x_i+x_{i+1}&\le 2\\ -y_{i,i+1}+x_i+x_{i+1}&\ge 0\\ y_{i,i+1} -x_i+x_{i+1}&\ge 0\\ y_{i,i+1} +x_i -x_{i+1}&\ge 0 \end{align}