IF a == b, then c = 1, else 0. How to turn this to a linear expression?

Question

I want to turn the following condition into a linear expression:

If a == b, then c = 1, else 0.

How should I transform this into a linear expression?

Thanks!

Answer 1

I assume by linear expression you mean an expression of the form $c = ma+nb + p$ where $m,n,p \in \mathbb{R}$, which satisfies the given condition.

Linear expressions are not powerful enough to capture such an expression. This can be proved without much effort (for example, put $(a=b=0)$, $(a=1,b=0)$ etc to get values of $m,n,p$ and finally arrive at a contradiction).

Essentially, you want a function $f$ from $\mathbb{R}\times\mathbb{R}$ which is the characteristic function of the set $\{(x,x) : x \in \mathbb{R}\}$. Perhaps if you give some context as to where this comes up and why you need a linear expression, I can be of more help.

Answer 2

Introduce three binary variables $d_1,d_2,d_3$ which sum to 1, and model the three possibilities

$$ a-b \leq M(1-d_1),~ -M(1-d_1) \leq c \leq M(1-d_1)\\ -M(1-d_2) \leq a - b \leq M(1-d_2),~ -M(1-d_2) \leq c-1 \leq M(1-d_2)\\ a-b \geq -M(1-d_3),~ -M(1-d_3) \leq c \leq M(1-d_3)\\ $$

If $a$ and $b$ are continuous, the model is not practically well-posed as you really cannot model equal vs not equal since solvers work with finite precision and tolerances around, say, $10^{-8}$. Hence, you would typically have to accept some region around equality where you think it is close enough, leading to

$$ a-b \leq -\epsilon + M(1-d_1),~ -M(1-d_1) \leq c \leq M(1-d_1)\\ -M(1-d_2)-\epsilon \leq a - b \leq \epsilon + M(1-d_2),~ -M(1-d_2) \leq c-1 \leq M(1-d_2)\\ a-b \geq \epsilon -M(1-d_3),~ -M(1-d_3) \leq c \leq M(1-d_3)\\ $$