I have an if-then-else condition with three binary variables A, B and C:
if A + B = 1 then C = 0
How do I express this as an integer linear program with equality constraints?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Your condition is effectively excluding $(0,1,1)$ and $(1,0,1)$ corners of the unit cube. Thinking of it pictorially gives you a quick formulation: (i) construct the cube, (ii) chop those corners off and (iii) ensure integrality.
In (ii), the corners we want to get rid of are on the $BC$ and $AC$ planes. We can cut from the correctly aligned diagonals on those planes. However, moving in $+A$ direction, the cut should shrink and vanish at $A=1$ to include $(1,1,1)$.
\begin{align*} &\text{(i) } 0 \leq A,B,C \leq 1 \\ &\text{(ii) }-A+B+C \leq 1, A-B+C \leq 1 \\ &\text{(iii) }A,B,C \in \{0,1\} \end{align*}
-
$\begingroup$ But with the inequations (ii) would it make it possible for both B and C exist and also A and C? Because this pairs can exist except C in the case of both A and B exist. $\endgroup$ Commented Jun 19, 2020 at 6:26
-
$\begingroup$ I'm confused, with the (A,B,C) notation, which points are you asking about? $\endgroup$ Commented Jun 19, 2020 at 6:32
-
$\begingroup$ I'm sorry, I meant if this way both B and C can exist (so both being equal to 1) OR both A and C can exist (so both being equal to 1). Because this pair can also exist $\endgroup$ Commented Jun 19, 2020 at 6:34
-
$\begingroup$ B and C can exist only if A also exists. Otherwise, i.e. if A=0, A+B=1 and C=1, which is against your condition. Similarly, A and C can exist only if B also does. So, (1,1,1) is feasible, but (1,0,1) and (0,1,1) are not feasible $\endgroup$ Commented Jun 19, 2020 at 6:41
-
1$\begingroup$ But if B and C exist that would be equal to 2 which is not inferior or equal to 1 like the inequation states. That is my concern $\endgroup$ Commented Jun 19, 2020 at 8:31