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?
$\begingroup$
$\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– David2017-06-09 02:04:38 +00:00Commented 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– asm_nerd12017-06-09 08:28:43 +00:00Commented Jun 9, 2017 at 8:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)]