# Formulate relationship between four binary variables

I have four binary variables $$x_{h}$$, $$x_{h'}$$, $$y_h$$ and $$y_{h'}$$. I need to have the following relationships satisfied between the variables:

1- If $$y_h = 1$$ and $$y_{h'} = 1$$, then exactly one of $$x_h$$ and $$x_{h'}$$ should be equal to 1 ($$y_h + y_{h'} = 2 \implies x_h + x_{h'} = 1$$).

2- If exactly one of $$y_h$$ and $$y_{h'}$$ is equal to 1, then both $$x_h$$ and $$x_{h'}$$ should be equal to 0 ($$y_h + y_{h'} = 1 \implies x_h + x_{h'} = 0$$).

3- If both $$y_h$$ and $$y_{h'}$$ are equal to 0, again both $$x_h$$ and $$x_{h'}$$ should be equal to 0 ($$y_h + y_{h'} = 0 \implies x_h + x_{h'} = 0$$).

I was thinking of a constraint like $$y_h + y_{h'} = 2 (x_h + x_{h'}),$$ however, it only considers relations 1 and 3.

How can I formulate this?

\begin{align}x_h + x_{h'} &\geq y_h + y_{h'} -1\\2 (x_h + x_{h'}) &\leq y_h + y_{h'}\end{align}

• This is awesome. Thanks mate. – Mostafa Apr 14 at 13:25
• This is correct, but you can strengthen the formulation by disaggregating the second constraint to: \begin{align}x_h+x_{h'}&\le y_h\\ x_h+x_{h'}&\le y_{h'}\end{align} – RobPratt Apr 14 at 14:14
• Thanks @RobPratt. Do you think your version will be easier to solve with commercial solvers? – Mostafa Apr 15 at 0:07
• Not sure. The effect probably depends on what the rest of your model looks like. The strengthened formulation would cut off solutions like $(1/2,0,3/4,1/4)$ that the weaker formulation allows. – RobPratt Apr 15 at 0:30

$$x_h + x_{h'} = y_h \times y_{h'},$$

But it is not linear anymore.

EDIT:

As suggested by TheSimpliFire (in a comment to my answer), you can refer to How to linearize the product of two binary variables? to linearize it.

• – TheSimpliFire Apr 14 at 9:38
• Thanks Betty and TheSimpliFire. Yes, I needed a linear one. – Mostafa Apr 14 at 10:59

Oh, I got the solution!

I add the constraint $$y_h + y_{h'} = x_h + x_{h'} + 1 - z.$$ Now, I should enforce $$z$$ to be 1 if $$y_h + y_{h'} = 0$$, and 0 otherwise. For that I add:

$$y_h + y_{h'} \leq M(1 - z),$$ where M is a sufficiently large number (I think 2 is enough!).

I don't remove the question since it may help someone sometime!

BTW, is there a better way to do this, possibly in a single constraint?

• Note here that you need additonally the constraint $z \geq 0$. Since you have an equation you can remove one variable from the system (here the new introduced one). So factor your equation for z, and plug them into $z \geq 0$ and your second inequality, then one arrives at the two inequalities i wrote in my answer. – user3680510 Apr 14 at 13:39
• Yes, yours is apparently better than mine. Actually, I have a large number of ($n^2 -n$) those constraits, that introducing $z$ results in the same number of additional variables. – Mostafa Apr 14 at 13:50