2
$\begingroup$

I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on their values, I want to have some other binary variables $y_1,\ldots,y_5$ activated according to the following table:

$y_1$ $y_2$ $y_3$ $y_4$ $y_5$
$d_1$ 1 0 0 1 1
$d_2$ 0 1 0 1 1
$d_3$ 0 0 1 0 1

For instance, $y_1$ is equal to 1 if and only if $d_1$ is equal to 1. Same goes for the pairs $(y_2,d_2)$ and $(y_3,d_3)$. $y_4$ becomes equal to 1 if both $d_1$ and $d_2$ are 1. Finally, $y_5$ becomes 1 if all of $d_1$, $d_2$ and $d_3$ are equal to 1.

Moreover, at the same time, only one of $y_1,\ldots,y_5$ can be activated, which is to formulate as $\sum y_i = 1$.

I am having problems though formulating the other constraints regarding the $d_i$, $y_i$ variables.

I have tried formulating the following set of constraints for $y_5$:

$$y_{\rm intermediate} \geq d_1 + d_2 - 1$$

This will allow $y_{\rm intermediate}$ to become 1 if both $d_1$ and $d_2$ are activated.

Then, I could have: \begin{align}y_5 &\geq y_{\rm intermediate} + d_3 - 1\\y_4&\geq y_{\rm intermediate} + (1 - d_3) - 1\end{align}

Then depending on the value of $d_3$ either $y_5$ or $y_4$ will become equal to 1.

However, I am having trouble formulating the rest of the constraints for $y_1$ to $y_3$ and I am also not sure if what I already have is good enough.

Does anyone have any pointers or ideas? Any help would be greatly appreciated.

$\endgroup$
6
$\begingroup$

If I understand correctly, the following enforces your desired behavior: \begin{align} y_1 &= d_1 \\ y_2 &= d_2 \\ y_3 &= d_3 \\ y_4 &\ge d_1 + d_2 - 1\\ y_5 &\ge d_1 + d_2 + d_3 - 2\\ \end{align} If you also want to enforce $y_4 \implies (d_1 \land d_2)$ and $y_5 \implies (d_1 \land d_2 \land d_3)$, then include these additional constraints: \begin{align} y_4 &\le d_1 \\ y_4 &\le d_2 \\ y_5 &\le d_1 \\ y_5 &\le d_2 \\ y_5 &\le d_3 \end{align}


On second thought, your comment about only one $y_i$ being activated makes me think that, instead of $y_1 = 1 \iff d_1 = 1$, you meant $y_1 = 1 \iff (d_1,d_2,d_3) = (1,0,0)$. Equivalently, $y_1 = d_1(1-d_2)(1-d_3)$, which you can linearize as follows: \begin{align} y_1 &\le d_1 \\ y_1 &\le 1 - d_2 \\ y_1 &\le 1 - d_3 \\ y_1 &\ge d_1 + (1 - d_2) + (1 - d_3) - 2 \end{align} You could similarly set up four linear inequality constraints for each of the other $y_i$ and then impose $y_1+y_2+y_3+y_4+y_5=1$. But a simpler formulation is just to treat the table entries as the constraint coefficients: \begin{align} y_1 + y_4 + y_5 &= d_1 \\ y_2 + y_4 + y_5 &= d_2 \\ y_3 + y_5 &= d_3 \\ y_1 + y_2 + y_3 + y_4 + y_5 &= 1 \end{align}

$\endgroup$

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.