2

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
worldsmithhelper
  • 4,007
  • 6
  • 21
  • 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. – joni Nov 15 '21 at 22:31
  • 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}. – worldsmithhelper Nov 15 '21 at 22:40
  • @worldsmithhelper, would you say, why not try to define integer variables whose bounds are limited to the ${-1,...,1}$ and linearizing with e.g. MacCormick method? Have you had any force to use boolean multiplication? – A.Omidi Mar 19 '24 at 14:09

1 Answers1

4

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84