2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – David
    Jun 9, 2017 at 2:04
  • $\begingroup$ @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. $\endgroup$
    – asm_nerd1
    Jun 9, 2017 at 8:28

1 Answer 1

3
$\begingroup$

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

Verifying in Haskell:

λ> triples = [ (x,y,z) | x <- [0,1], y <- [0,1], z <- [0,1] ]
λ> filter (\(x,y,z)->(-x+y>=0) && (x-y+z>=0) && (y-z>=0)) triples
[(0,0,0),(0,1,1),(1,1,0),(1,1,1)]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.