## Friday, December 21, 2018

### An interesting linearization involving xor

 XOR gate sold by Amazon [1]

In [2] a question was asked:

How can we solve $x^TAy = b$ for $$x_i, y_i \in \{-1,+1\}$$?

In this post I will discuss three different formulations:

1. A simple quadratic formulation yielding a non-convex MIQCP model
2. A MIP model based on a standard linearization
3. A MIP model based on a linearization using an xor construct

#### Test Data

To help with some test models we need some data for $$A$$ and $$b$$. Here is an instance that actually has a solution (printed with 3 decimals):

----     13 PARAMETER a

i1          i2          i3          i4          i5

i1       0.998       0.579       0.991       0.762       0.131
i2       0.640       0.160       0.250       0.669       0.435
i3       0.360       0.351       0.131       0.150       0.589
i4       0.831       0.231       0.666       0.776       0.304
i5       0.110       0.502       0.160       0.872       0.265

----     13 PARAMETER b                    =        2.222


Notice that solutions are not unique: if we have a solution $$(x,y)$$ then another solution is $$(-x,-y)$$.

#### MIQCP Model

The simplest is to use a Mixed-Integer Quadratically Constrained (MIQCP) model that handles the quadratic equation directly. Of course, in optimization we prefer binary variables $$z \in\{0,1\}$$ instead of $$z \in\{-1,+1\}$$. That is easily fixed: introduce binary variables $$p_i, q_i$$ and write: \begin{align}&x_i = 2p_i-1\\&y_i = 2q_i-1\\&p_i,q_i \in\{0,1\}\end{align} This maps a binary variable to $$\{-1,+1\}$$. So a MIQCP model can look like:

MIQCP Formulation
\begin{align} & \sum_{i,j} \color{DarkRed} x_i \color{DarkRed}y_j \color{DarkBlue}a_{i,j} = \color{DarkBlue}b \\ & \color{DarkRed}x_{i} = 2\color{DarkRed}p_{i}-1\\ & \color{DarkRed}y_{i} = 2\color{DarkRed}q_{i}-1\\ & \color{DarkRed}p_i, \color{DarkRed}q_i \in\{0,1\} \end{align}

This is a non-convex problem, so you need a global solver like Baron, Couenne or Antigone. Most quadratic solvers only support the much easier, convex case. When expressing this feasibility problem as an optimization problem, we need to add a dummy objective. The solution can look like:

----     55 VARIABLE p.L

i1 1.000,    i4 1.000,    i5 1.000

----     55 VARIABLE q.L

i1 1.000,    i2 1.000,    i4 1.000

----     55 VARIABLE x.L

i1  1.000,    i2 -1.000,    i3 -1.000,    i4  1.000,    i5  1.000

----     55 VARIABLE y.L

i1  1.000,    i2  1.000,    i3 -1.000,    i4  1.000,    i5 -1.000

----     59 PARAMETER b2                   =        2.222  x'Ay using solution values


We find a solution that when plugged into $$x^TAy$$, reproduces our right-hand side.

#### Linearization 1

This problem can be linearized. This will allow us to use a linear MIP solver. One way is to write:$\sum_{i,j} x_i y_j a_{i,j} = \sum_{i,j} (2p_i-1)(2q_j-1) a_{i,j} = \sum_{i,j} \left( 4 p_i q_j - 2 p_i -2q_j + 1 \right) a_{i,j}$

The binary product $$v_{i,j} = p_i q_j$$ can be linearized using a standard formulation [3]: \begin{align} &v_{i,j} \le p_i\\ &v_{i,j} \le q_j \\ & v_{i,j} \ge p_i + q_j -1 \\ & p_i, q_j, v_{i,j} \in \{0,1\} \end{align} Combining this leads to:

MIP Formulation I
\begin{align} & \sum_{i,j} \left( 4 \color{DarkRed} v_{i,j} - 2 \color{DarkRed}p_i -2 \color{DarkRed} q_j + 1 \right) \color{DarkBlue} a_{i,j} = \color{DarkBlue}b \\ & \color{DarkRed}v_{i,j} \le \color{DarkRed}p_i\\ & \color{DarkRed}v_{i,j} \le \color{DarkRed}q_j \\ & \color{DarkRed}v_{i,j} \ge \color{DarkRed}p_i + \color{DarkRed}q_j -1 \\ & \color{DarkRed}x_{i} = 2\color{DarkRed}p_{i}-1\\ & \color{DarkRed}y_{i} = 2\color{DarkRed}q_{i}-1\\ & \color{DarkRed}p_i, \color{DarkRed}q_i, \color{DarkRed}v_{i,j} \in\{0,1\} \end{align}

It is noted that $$v$$ can be relaxed to be continuous between 0 and 1: $$v_{i,j} \in [0,1]$$. The solution can look like:

----     62 VARIABLE p.L

i1 1.000,    i4 1.000,    i5 1.000

----     62 VARIABLE q.L

i1 1.000,    i2 1.000,    i4 1.000

----     62 VARIABLE v.L  v(i,j)=p(i)*q(j)

i1          i2          i4

i1       1.000       1.000       1.000
i4       1.000       1.000       1.000
i5       1.000       1.000       1.000

----     62 VARIABLE x.L

i1  1.000,    i2 -1.000,    i3 -1.000,    i4  1.000,    i5  1.000

----     62 VARIABLE y.L

i1  1.000,    i2  1.000,    i3 -1.000,    i4  1.000,    i5 -1.000

----     66 PARAMETER b2                   =        2.222  x'Ay using solution values


Note that zeroes are not printed here (so the matrix $$v$$ may look a bit strange).

#### Linearization 2

There is another linearization which is more interesting. For this we will use the binary xor operator.

There are different ways xor is denoted. I believe the most common ones are \begin{align} & z = x \textbf{ xor } y\\ & z = \textbf{xor}(x,y) \\ & z = x \oplus y \\ & z = x \veebar y\end{align} The xor truth table is: $\begin{matrix} \textbf{ x } & \textbf{ y } & \textbf{ z }\\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\\ 1 & 1 & 0 \end{matrix}$I.e. $$z = x \textbf{ xor } y$$ is 1 if and only if $$x$$ and $$y$$ are different.

Now consider the following thruth-table:

----     15 PARAMETER t  truth-table

x           y         x*y           p           q     p xor q   1 - 2 xor

i1          -1          -1           1                                               1
i2          -1           1          -1                       1           1          -1
i3           1          -1          -1           1                       1          -1
i4           1           1           1           1           1                       1


From this we can see that $x_i y_j = 1 - 2 (p_i \textbf{ xor } q_j)$ So our quadratic constraint becomes $\sum_{i,j} x_i y_j a_{i,j} = \sum_{i,j} \left( 1 - 2 (p_i \textbf{ xor } q_j) \right) a_{i,j} = b$ The operation $$w_{i,j} = p_i \textbf{ xor } q_j$$  can be linearized [4]: \begin{align} & w_{i,j} \le p_i + q_j \\& w_{i,j} \ge p_i - q_j \\& w_{i,j} \ge q_j - p_i \\& w_{i,j} \le 2 - p_i - q_j \\ & p_i, q_j, w_{i,j} \in \{0,1\} \end{align} With these tools we can formulate a different linearization:

MIP Formulation II
\begin{align} & \sum_{i,j} \left( 1 - 2 \color{DarkRed} w_{i,j} \right) \color{DarkBlue} a_{i,j} = \color{DarkBlue}b \\ & \color{DarkRed}w_{i,j} \le \color{DarkRed}p_i + \color{DarkRed}q_j\\ & \color{DarkRed}w_{i,j} \ge \color{DarkRed}p_i - \color{DarkRed}q_j \\ & \color{DarkRed}w_{i,j} \ge \color{DarkRed}q_j - \color{DarkRed}p_i \\ & \color{DarkRed}w_{i,j} \le 2 - \color{DarkRed}p_i - \color{DarkRed}q_j \\ & \color{DarkRed}x_{i} = 2\color{DarkRed}p_{i}-1\\ & \color{DarkRed}y_{i} = 2\color{DarkRed}q_{i}-1\\ & \color{DarkRed}p_i, \color{DarkRed}q_i, \color{DarkRed}w_{i,j} \in\{0,1\} \end{align}

It is noted that $$w$$ can be relaxed to be continuous between 0 and 1: $$w_{i,j} \in [0,1]$$. A solution can look like:

----     62 VARIABLE p.L

i1 1.000,    i4 1.000,    i5 1.000

----     62 VARIABLE q.L

i1 1.000,    i2 1.000,    i4 1.000

----     62 VARIABLE w.L  w(i,j) = p(i) xor q(j)

i1          i2          i3          i4          i5

i1                               1.000                   1.000
i2       1.000       1.000                   1.000
i3       1.000       1.000                   1.000
i4                               1.000                   1.000
i5                               1.000                   1.000

----     62 VARIABLE x.L

i1  1.000,    i2 -1.000,    i3 -1.000,    i4  1.000,    i5  1.000

----     62 VARIABLE y.L

i1  1.000,    i2  1.000,    i3 -1.000,    i4  1.000,    i5 -1.000

----     66 PARAMETER b2                   =        2.222  x'Ay using solution values


#### Conclusion

I am somewhat surprised how different the two linearizations look. You would not easily recognize that the two different linear formulations are essentially the same. I don't remember many times I could use an xor operation in an optimization (I used it to solve Takuzu puzzles in [5]). The second linearization earns extra points for using xor!

This question was more interesting than I anticipated.

#### References

1. A Fairchild/ON Semiconductor XOR gate sold by Amazon for \$1.69. https://www.amazon.com/Logic-Gates-2-Input-XOR-Gate/dp/B00MEKUZV8
2. Matrix Equation & Integer Programming, https://math.stackexchange.com/questions/3047086/matrix-equation-integer-programming/3047835
3. Multiplication of Binary Variables, https://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-binary-variables.html
4. XOR as linear inequalities, https://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html
5. Solving Takuzu puzzles as a MIP using xor, https://yetanothermathprogrammingconsultant.blogspot.com/2017/01/solving-takuzu-puzzles-as-mip-using-xor.html