Linearize x different of y in ILP

Question

I am surprised I couldn't find an already written answer for my question in the internet.

I want to linearize $x$ different of $y$ for two nonegative integer decision variables. I am not considering using Constraint Programming which I know that it is better for such constraints, only ILP.

My idea was that I use two sets of constraints:

$x \ge y + 0.5 \text{ OR } x \le y - 0.5$

Then, with binary variable $z$ and $M$ rightly chosen constant depending on the domains of $x$ and $y$:

$x \ge (y + 0.5)z$

$x \le (y - 0.5) + Mz$

Then linearize the first constraint.

However, one of my friend suggested me: "compute $x-y$ and $y-x$, take maximum value of these two variables, for instance using this next picture:

And then you have the distance between $x$ and $y$ which you impose to be positive.

What is the best way?

Answer 1

I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint $(1)$ enforces $z=0 \implies x + 1 \le y$. Constraint $(2)$ enforces $z=1 \implies y + 1 \le x$.

This idea goes back at least to Manne, On the Job-Shop Scheduling Problem (1960).

In some modeling languages, you can also enforce these implications by using indicator constraints.