2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It is a minimum capacitated facility location problem in disguise - strictly speaking one of its steps. You need to choose combinations of edges for each client such that all necessary resources are present. There are usually multiple such combinations. so variables are edges. But in order to maximize the cost only 120 seconds given so additional variables do not let one solve the problem in given time $\endgroup$ – Tom Apr 11 '17 at 18:14
  • $\begingroup$ yes. It is important that at most 1 of them is true $\endgroup$ – Tom Apr 11 '17 at 18:56
  • $\begingroup$ Only the fact that my assignment should be solvable but it does not manage to complete in 120 seconds, so I thought there must be a way to encode the problem more efficiently. As long as any other way adds more variables (and running time) - i am trying to figure out if it is possible $\endgroup$ – Tom Apr 11 '17 at 21:04
  • 1
    $\begingroup$ Can you edit the question to clarify what you want? For instance, suppose all variables are true (1,2,3,4): does that satisfy the condition? Based on the formula you give (1 and 2) or (2 and 3 and 4) or (1 and 4)) I was guessing that the answer is "yes", but based on your "Basically.." it sounds like the answer might be "no". Can you edit the question to be clearer, and to be internally self-consistent? $\endgroup$ – D.W. Apr 11 '17 at 22:03
  • $\begingroup$ D.W., I think the only thing i did not state clearly is that it should be at most one (so choice among these 3 exact sets). I intend to extend your suggestions with orlp to the problem of 100 clients, 400 facilities, and there there will be more than 20 clauses with more than 20-30 variables, so i need to think first what your answers are and how i can use them $\endgroup$ – Tom Apr 11 '17 at 22:30
3
$\begingroup$

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.

Interpretation #1:

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

Interpretation #2:

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

$\endgroup$
  • $\begingroup$ If only the variables are required to be binary, and not the constants, I have a solution with only 4 equations that works. $\endgroup$ – orlp Apr 11 '17 at 21:47
  • $\begingroup$ I haven't tested your original version but neither version in your edited answer works. (1, 1, 1, 1) is a counterexample to both. $\endgroup$ – orlp Apr 11 '17 at 21:58
  • $\begingroup$ $(1, 1, 1, 1)$ is the equivalent of $\{1, 2, 3, 4\}$ in the original question, which is not in the accepted set of sets. $\endgroup$ – orlp Apr 11 '17 at 22:00
  • 1
    $\begingroup$ D.W., orlp is right. It is AT MOST one out of, so 2nd interpretation is correct. $\endgroup$ – Tom Apr 11 '17 at 22:26
  • 1
    $\begingroup$ @RodrigodeAzevedo, Nothing particularly interested or exciting. I used brute force search over all inequalities with coefficients in {-1,0,1}, combined with minimization (finding the smallest subset, through a heuristic). $\endgroup$ – D.W. Apr 13 '17 at 18:38
2
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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)]
$\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.