1
$\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$
  • $\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 '17 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$ – Abubakar Siddique Jun 9 '17 at 8:28
2
$\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, privacy policy and cookie policy

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