linearizing a constraint involving an absolute function

I would like to know what is the best way to linearize a constraint involving an absolute function. More precisely, imagine I have three binary variables and their relationships is as follows:

|x-y| = z.

I have so many z variables that it's value depends on x and y (all binary). That's why I am looking for an efficient way (bigM or any other way) to model efficiently this constraint.

Note that this is the same relationship as $$x \text{ xor } y=z$$. You want to enforce four logical implications: \begin{align} x \land y &\implies \lnot z \\ x \land \lnot y &\implies z \\ \lnot x \land y &\implies z \\ \lnot x \land \lnot y &\implies \lnot z \end{align} Via conjunctive normal form or otherwise, the resulting linear constraints are: \begin{align} (1-x)+(1-y)+(1-z) &\ge 1 \\ (1-x)+y+z &\ge 1 \\ x+(1-y)+z &\ge 1 \\ x+y+(1-z) &\ge 1 \end{align} You can optionally relax $$z$$ to be nonnegative, and it will automatically take binary values.

Alternatively, you can think of the desired relationship as $$x+y\mod 2=z$$ and impose a single equality constraint $$x+y=z+2w$$, where $$w$$ is binary.

• I tried the formulation and they both works. Thanks for your help !
– Sam
Apr 2 at 9:26

Try this:
$$z \le 2 - (x+y)$$
$$x-y \le z$$
$$y-x \le z$$
$$z \le x+y$$

• What you proposed is equivalent to $x+y+z=2$, which incorrectly prevents $(x,y,z)=(0,0,0)$. Apr 1 at 12:38
• I see the possibility of $0$s Apr 1 at 16:10
• In your formulation, if $x=0$ and $y=0$ then $z=2\not=0$. Apr 1 at 16:27
• true, true, it was late in the night didnt think through, let me see if I can come with an alternative. Apr 1 at 16:40
• Now what you have is the same formulation I proposed. Apr 1 at 19:18