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
    Commented 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
    Commented Apr 1 at 12:38
  • $\begingroup$ I see the possibility of $0$s $\endgroup$ Commented Apr 1 at 16:10
  • $\begingroup$ In your formulation, if $x=0$ and $y=0$ then $z=2\not=0$. $\endgroup$
    – RobPratt
    Commented 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$ Commented Apr 1 at 16:40
  • $\begingroup$ Now what you have is the same formulation I proposed. $\endgroup$
    – RobPratt
    Commented 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.