Linear Programing: Set binary variable 1, if two variables are not equal

Question

I guess I have a simple problem, but I can't find a fitting solution.

I have a certain amount periods $D$, and every period is described by the decision variable $X_d$. What I want to do is set a binary Variable $N_d$ to 1, if the value $X_d$ is not equal to $X_{d-1}$. So if the value $X$ changes between two periods, the binary variable should be $1$. If it stays the same, the binary variable should be $0$.

So far I'm struggeling with not being allowed to use the absolute value of the difference of $X_d$ and $X_{d-1}$ to keep the problem linear.

My first idea was: $$ |X_{d-1} - X_d| \times 0.01 \leq N_d \quad \textrm{for } d > 1 $$

I hope you can understand my problem and I would appreciate any help!

Best regards, Seba

Answer 1

What about $$ (X_{d-1} - X_d)^2 \ ? $$

I'm assuming that you're talking about linearity of coefficients, instead of linearity of measures.

Answer 2

The following formulation assumes that $X_d$ and $X_{d-1}$ are binary variables.

You can enforce the implication $X_d \not= X_{d-1} \implies N_d = 1$ by introducing these two linear constraints: \begin{align*} X_d - X_{d-1} &\le N_d \\ X_{d-1} - X_d &\le N_d \end{align*} You can enforce the implication $N_d = 1 \implies X_d \not= X_{d-1}$ by introducing these two linear constraints: \begin{align*} X_d + X_{d-1} &\le 2 - N_d \\ X_d + X_{d-1} &\ge N_d \end{align*}

Edit: The following formulation assumes that $X_d$ and $X_{d-1}$ are integer variables bounded by 0 and 48.

Introduce binary variables $N_d^1$, $N_d^2$, and $N_d^3$ and linear constraints: \begin{align} X_d - X_{d-1} &\ge -48 N_d^1 + N_d^3 \\ X_d - X_{d-1} &\le - N_d^1 + 48 N_d^3 \\ \sum_{i=1}^3 N_d^i &= 1 \\ N_d &= N_d^1 + N_d^3 \end{align}

To see that this works, consider the three cases $(N_d^1,N_d^2,N_d^3)=(1,0,0)$, $(0,1,0)$, and $(0,0,1)$.

As long as you impose an upper bound of 1 on $N_d$, you can omit $N_d^2$ and constraint (3).