4
$\begingroup$

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?

Improve this question
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is awesome. Thanks mate. $\endgroup$ – Mostafa Apr 14 '20 at 13:25
  • 2
    $\begingroup$ 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} $\endgroup$ – RobPratt Apr 14 '20 at 14:14
  • $\begingroup$ Thanks @RobPratt. Do you think your version will be easier to solve with commercial solvers? $\endgroup$ – Mostafa Apr 15 '20 at 0:07
  • 2
    $\begingroup$ 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. $\endgroup$ – RobPratt Apr 15 '20 at 0:30
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
2
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – user3680510 Apr 14 '20 at 13:39
  • $\begingroup$ 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. $\endgroup$ – Mostafa Apr 14 '20 at 13:50

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.