4

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?

Community
  • 1
Mostafa
  • 2,104
  • 10
  • 28

3 Answers3

4

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

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
user3680510
  • 3,655
  • 6
  • 26
  • This is awesome. Thanks mate. – Mostafa Apr 14 '20 at 13:25
  • 2
    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 '20 at 14:14
  • Thanks @RobPratt. Do you think your version will be easier to solve with commercial solvers? – Mostafa Apr 15 '20 at 00:07
  • 2
    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 '20 at 00:30
3

How about:

$$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.

Betty
  • 544
  • 4
  • 16
2

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?

Mostafa
  • 2,104
  • 10
  • 28
  • 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 '20 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 '20 at 13:50