Converting If-else integer equation to Linear Programming

Question

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?

Answer 1

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*}

• Filipaaaaa: 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.
• altugkarakurt: I'm confused, with the (A,B,C) notation, which points are you asking about?
• Filipaaaaa: 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
• altugkarakurt: 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
• Filipaaaaa: 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