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