0
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I tried the formulation and they both works. Thanks for your help ! $\endgroup$
    – Sam
    Apr 2 at 9:26
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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