Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have multiple sets, e.g.,
$$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$
Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables
$$(1 \land 2) \lor (2 \land 3 \land 4) \lor (1 \land 4)$$
Basically, I need to enforce that either $1$ and $2$ are 1s, or $2$ and $3$ and $4$ are ones, or $1$ and $4$ are 1s, but not all of them. Constants can be added as needed, as well as equalities, inequalities, etc. How can I do that?
You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy your condition. (That's because any system of linear inequalities forms a convex polytope.)
It's not quite clear to me from your question about what your condition is, so I'll try answering your question with both plausible interpretations I see.
In the first possible interpretation, the boolean formula is $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$. This means the polytope needs to contain all of the following seven points:
$$(0,1,1,1), (1,0,0,1), (1,0,1,1), (1,1,0,0), (1,1,0,1), (1,1,1,0), (1,1,1,1)$$
and not any of the other nine points where the formula is false.
There are various ways to check whether there exists such a polytope. One way is to enumerate all possible inequalities $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 + c_5 \ge 0$ and look for combinations $(c_1,\dots,c_5)$ such that this inequality is true for all of the seven points listed above. Then, we check whether a system of constraints obtained by using all of those inequalities has the desired property (in particular, each of the other nine points violates at least one of these inequalities). You can then minimize the set of constructed inequalities, to remove redundancies.
Here is one such system of constraints that works:
$$\begin{align*} x_2+x_4-1 &\ge 0\\ x_1+x_3-1&\ge 0\\ x_1+x_2-x_3+x_4-1 &\ge 0 \end{align*}$$
Another way to have obtained this system of constraints would be to convert the DNF formula you listed to CNF, and then translate each "OR" constraint into a single inequality using the techniques from Express boolean logic operations in zero-one integer linear programming (ILP). The formula $(x_1 \land x_2) \lor (x_2 \land x_3 \land x_4) \lor (x_1 \land x_4)$ is equivalent to $(x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_1 \lor x_4) \land (x_2 \lor x_4)$. That then yields the following system of constraints, which also works:
$$\begin{align*} x_1+x_2-1 &\ge 0\\ x_1+x_3-1 &\ge 0\\ x_1+x_4-1 &\ge 0\\ x_2+x_4-1 &\ge 0 \end{align*}$$
In the second plausible interpretation, you want the boolean formula
$$(x_1 \land x_2 \land \neg x_3 \land \neg x_4) \lor (\neg x_1 \land x_2 \land x_3 \land x_4) \lor (x_1 \land \neg x_2 \land \neg x_3 \land x_4).$$
Thus, you want the polytope to contain only the three points
$$(1,1,0,0),(0,1,1,1),(1,0,0,1).$$
We can apply the same methods to get a system of inequalities for this formula. Here is one solution that works:
$$\begin{align*} -x_1-x_3+1 &\ge 0\\ -x_2+x_3-x_4+1 &\ge 0\\ x_2+x_4-1 &\ge 0\\ x_1+x_3-1 &\ge 0\\ x_1+x_2-x_3+x_4-1 &\ge 0 \end{align*}$$
(1, 1, 1, 1) is a counterexample to both.
$\endgroup$
I will use a = 1, b = 2, etc...
If a is set then c must be false and EITHER b or d must be true:
10a + c <= 10
10a + b + d <= 11
10a - b - d <= 9
Finally, if a is not set then the rest must be true:
10 - 10a - b - c - d <= 7
To complement the 2nd part of D.W.'s answer, we would like to find an $\mathcal H$-polytope (defined by the intersection of closed half-spaces) whose intersection with $\{0,1\}^4$ is
$$\{ (1,1,0,0),(0,1,1,1),(1,0,0,1) \}$$
Let
$$\Phi := \left(x_{1} \wedge x_{2} \wedge \neg x_{3} \wedge \neg x_{4}\right) \vee \left(\neg x_{1} \wedge x_{2} \wedge x_{3} \wedge x_{4} \right) \vee \left(x_{1} \wedge \neg x_{2} \wedge \neg x_{3} \wedge x_{4}\right)$$
Using SymPy,
>>> from sympy import *
>>> x1, x2, x3, x4 = symbols('x1 x2 x3 x4')
>>> Phi = (x1 & x2 & Not(x3) & Not(x4)) | (Not(x1) & x2 & x3 & x4) | (x1 & Not(x2) & Not(x3) & x4)
Converting to the CNF,
>>> to_cnf(Phi,simplify=true)
And(Or(x1, x2), Or(x1, x3), Or(x1, x4), Or(x2, x4), Or(x2, Not(x3)), Or(x4, Not(x3)), Or(Not(x1), Not(x3)), Or(x3, Not(x2), Not(x4)))
Hence,
$$\Phi \equiv \left(x_{1} \vee x_{2}\right) \wedge \left(x_{1} \vee x_{3}\right) \wedge \left(x_{1} \vee x_{4}\right) \wedge \left(x_{2} \vee x_{4}\right) \wedge \left(x_{2} \vee \neg x_{3}\right) \wedge \left(x_{4} \vee \neg x_{3}\right) \wedge \left(\neg x_{1} \vee \neg x_{3}\right) \wedge \left(x_{3} \vee \neg x_{2} \vee \neg x_{4}\right)$$
Note that $\neg x_i$ and $x_i \vee x_j$ can be translated into binary integer programming as $1 - x_i$ and $x_i + x_j \geq 1$, respectively. Thus, an $\mathcal H$-polytope with the desired property is defined as follows
$$\begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & -1 & 0\\ 0 & 0 & -1 & 1\\ -1 & 0 & -1 & 0\\ 0 & -1 & 1 & -1\end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\end{bmatrix} \geq \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 0\\ 0\\ -1\\ -1\end{bmatrix}$$
Verifying in Haskell:
λ> filter (\(x1,x2,x3,x4)->(x1 + x2 >= 1 && x1 + x3 >= 1 && x1 + x4 >= 1 && x2 + x4 >= 1 && x2 - x3 >= 0 && -x3 + x4 >= 0 && -x1 - x3 >= -1 && -x2 + x3 - x4 >= -1)) [ (x1,x2,x3,x4) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1] ]
[(0,1,1,1),(1,0,0,1),(1,1,0,0)]
It seems to be correct. However, note that D.W.'s polytope is more economical, as it only uses $5$ half-spaces, whereas my polytope uses $8$ half-spaces. Verifying D.W.'s polytope:
λ> filter (\(x1,x2,x3,x4)->(-x1 - x3 >= -1 && -x2 + x3 - x4 >= -1 && x2 + x4 >= 1 && x1 + x3 >= 1 && x1 + x2 - x3 + x4 >= 1)) [ (x1,x2,x3,x4) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1] ]
[(0,1,1,1),(1,0,0,1),(1,1,0,0)]
