Friday, April 26, 2013
So multiplication is generally not linearizable. However you can linearize binary multiplication. Let's assume x and y is two binary variables (either 0 or 1), we can linearize z = x*y as follow:
z <= x;
z <= y;
z >= x+y-1;
z >= 0;
Further more you can use this trick to multiply two variables x and y with value {-1,1}. Here is the trick is noticing if x and y is equal then multiplication z is 1 otherwise it is -1. Thus we can map variable x to {0,1} by (x+1)/2 or we can use binary variable to generate variables with value {-1,1} by 2*binary-1. After we get binary variable x' and y', we multiply them as above to get z'. And we may flip x' and y', to get x'' and y'' as x''=(1-x'); and we may multiply them as show above as well to get z''. If we add z' and z'', we get sum which is 1 if both values of x and y are same (1,1 or -1,-1) and 0 if they are different (-1,1 or 1,-1). We may map sum to correct result by final_result=(2*sum-1)formula. Bellow you may find a truth table:
Truth Table
|
|||||||||
x'
|
y'
|
z'
|
x''
|
y''
|
z''
|
sum
|
x
|
y
|
z
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
-1
|
-1
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
-1
|
1
|
-1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
-1
|
-1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
Reference: Linearization in Mathematical Programming
