# Converting if-then-else condition to integer linear programming with equality constraints

I have an if-then-else condition with three binary variables $A$, $B$ and $C$:

if A = 1
then B = 1
else
B = C


How do I express this as an integer linear program with equality constraints?

• I'm not totally clear on what you're asking... Linear programming solves (linear) optimization problems: problems where there is an objective function that must be either maximized or minimized. Is there a broader context to the question (what are you trying to maximize/minimize)? – David Jun 9 '17 at 2:04
• @DavidYoung, this is something similar to [this] (cs.stackexchange.com/questions/71091/…), however I could not guess how to convert my problem into a linear programming constraint. – Abubakar Siddique Jun 9 '17 at 8:28

We have three binary variables $x, y, z \in \{0,1\}$ and the following if-then-else (ITE) condition

$$\text{if } x = 1 \text{ then } y = 1 \text{ else } y = z$$

If $x = 1$, then $y = 1$ but $z \in \{0,1\}$. If $x = 0$, then $y = z \in \{0,1\}$. Therefore, we have the following $4$ vertices of the $3$-cube

$$\{ (0,0,0), (0,1,1), (1,1,0), (1,1,1) \}$$

Using SymPy, we obtain the following product of sums (POS):

>>> from sympy import *
>>> x, y, z = symbols('x y z')
>>> minterms = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]]
>>> POSform([x, y, z], minterms, [])
And(Or(Not(x), y), Or(Not(y), x, z), Or(Not(z), y))


Converting the formula in POS, i.e., in conjunctive normal form (CNF), to integer programming, we obtain the following system of linear inequalities

$$\begin{array}{rl} (1-x) + y &\geq 1\\ x + (1-y) + z &\geq 1\\ y + (1-z) &\geq 1\end{array}$$

which can be rewritten as follows

$$\begin{array}{rl} -x + y &\geq 0\\ x - y + z &\geq 0\\ y -z &\geq 0\end{array}$$

λ> triples = [ (x,y,z) | x <- [0,1], y <- [0,1], z <- [0,1] ]