Linear Optimization: Absolute difference between binary vectors

Question

The decision variable of my optimization problem (which I am aiming at keeping linear) is a placement binary vector, where the value in each position is either 0 or 1 (two different possible locations of item i).

One component of the objective function is this:

C_T is the const of transferring N items.

k is the iteration in which I am currently solving the problem and k-1 is the current displacement of items (result of solving the last iteration of the problem k-1). I have an initial condition (k=0).

N is "how many positions of x are different between the current displacement (k-1) and the outcome of the optimization problem (future optimal displacement x^k)".

How can I keep this component of the objective function linear? In other words, how can I replace the XOR operator? I thought about using the absolute difference as an alternative but I'm not sure it will help.

Is there a linear way to do this?

I will implement this problem with PuLP in python, maybe there is something that can help over there as well...

Answer 1

My notation is: xprev[i] is the previous solution and x[i] is the current one. I assume xprev[i] is a binary constant and x[i] is a binary variable. Then we can write

   sum(i, |xprev[i]-x[i]|) 
   =sum(i|xprev[i]=0, x[i]) + sum(i|xprev[i]=1, 1-x[i]) 
   =sum(i, x[i]*(1-xprev[i]) + (1-x[i])*xprev[i])  

Both the second and third lines can be implemented directly in Pulp. Note that | in the second line is 'such that'.

---

Below we have a comment that claims this is wrong. So let's write my expression as B*(1-A)+(1-B)*A. The following truth table can be constructed:

 A   B   A xor B    B*(1-A)+(1-B)*A
 0   0      0          0   +   0  
 0   1      1          1   +   0  
 1   0      1          0   +   1
 1   1      0          0   +   0

Note that A xor B = A*not(B) + not(A)*B is a well-known identity.

---

Note. Here I used the assumption that xprev[i] (or A) is a constant so things are linear. If both are (boolean) variables (let's call them x and y), then we need to do something differently. We can linearize the construct z = x xor y using four inequalities:

z <= x + y
z >= x - y
z >= y - x
z <= 2 - x - y

This is now linear can be used inside a MIP solver.