1
$\begingroup$

Suppose we have a Boolean expression $$(\neg x_{1}\wedge\neg x_{2})\vee\left(\neg x_{1}\wedge\neg x_{3}\right),$$ which we need to be true. Is there a method to convert this to a linear expression of the form $$a_1x_1+a_2x_2+a_3x_3<1,$$ $$x_1,x_2,x_3\in\{0,1\}$$where $a_1,a_2,a_3$ are real constants. Such that the Boolean expression is satisfied iff the integer linear expression is satisfied. The question is how to find $a_1,a_2,a_3$ uniquely? There is a method to convert later linear expression into the Boolean expression but we need other way around.

Thanks a lot.

$\endgroup$
2
$\begingroup$

You may take

$$ f(x_1,x_2,x_3)=(1+\varepsilon)x_1+(1-\varepsilon)(x_2+x_3) $$

where $\varepsilon \in (0,\frac{1}{2})$ is a constant.

When $(x_1,x_2,x_3)$ satisfies your condition, one has $f(x_1,x_2,x_3) \leq 1-\varepsilon$.

When $(x_1,x_2,x_3)$ does not satisfy your condition, one has $f(x_1,x_2,x_3) \geq 2(1-\varepsilon)$.

Note that there is no “uniqueness”.

$\endgroup$
  • $\begingroup$ Thanks a lot. we were going for uniqueness but I guess it can't be done. $\endgroup$ – triomphe Dec 1 '13 at 15:04
0
$\begingroup$

One approach to get a system of linear constraints is to rewrite the logical proposition in conjunctive normal form and then read off the linear constraints: \begin{align} &(\neg x_1 \wedge \neg x_2) \vee (\neg x_1 \wedge \neg x_3) \\ &\neg x_1 \bigwedge (\neg x_2 \vee \neg x_3) \\ &(1 - x_1 \ge 1) \bigwedge (1 - x_2 + 1 - x_3 \ge 1) \\ &(x_1 \le 0) \bigwedge (x_2 + x_3 \le 1) \\ \end{align}

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