Constraints that set values to binary variables depending on other binaries

Question

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.

Answer 1

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}