2
$\begingroup$

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:

enter image description here

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

What is the best way?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.