2
$\begingroup$

I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ possibly with a constraint like $1\geq B_1 + B_2$ or $1 \leq B_1 + B_2$ to get rid of double encoding of $0$ when found helpful.

I tried to find a way to construct this using the linearization of the product of Booleans but I found no way to do so elegantly (that is do so without implementing the CNF of the Karnaugh diagram for $B_1$, $B_2$ of the result). The fact that such a CNF encoding is possible suggests that there might exist a more appropriate formulation for MILP.

$\endgroup$
2
  • $\begingroup$ What about $$ x \cdot y = (x_1 - x_2) \cdot (y_1 - y_2) = x_1y_1 - x_1y_2 - x_2y_1 + x_2y_2, $$ where $x_1,x_2,y_1, y_2$ are binary? Here, you can easily linearize the products of binary variables. $\endgroup$
    – joni
    Nov 15, 2021 at 22:31
  • $\begingroup$ Can you submit that as an answer? I see 3 new variables being introduced when the double representationof 0 is being resolved which is good. I would wait a bit longer and see if there is a more succint answer in terms of {-1,0,1}. $\endgroup$ Nov 15, 2021 at 22:40

1 Answer 1

4
$\begingroup$

If you write $x=B_1-B_2$, $y=B_3-B_4$, and $z=B_5-B_6$ and supply the nine solutions for which $z=x\cdot y$, $B_1+B_2 \le 1$, $B_3+B_4 \le 1$, and $B_5+B_6 \le 1$, PORTA returns $B_i \ge 0$ and the following seven inequalities: \begin{align} - B_1 - B_3 + B_6 &\le 0 \\ - B_1 - B_4 + B_5 &\le 0 \\ - B_2 - B_3 + B_5 &\le 0 \\ - B_2 - B_4 + B_6 &\le 0 \\ - B_1 - B_2 + B_5 + B_6 &\le 0 \\ - B_3 - B_4 + B_5 + B_6 &\le 0 \\ B_1 + B_2 + B_3 + B_4 - B_5 - B_6 &\le 1 \end{align} The resulting system has only the nine originating solutions.

$\endgroup$
1

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.