线性优化：二元向量之间的绝对差
Linear Optimization: Absolute difference between binary vectors
我的优化问题（我的目标是保持线性）的决策变量是一个放置二进制向量，其中每个位置的值是 0 或 1（项目 i 的两个不同可能位置）。
objective 函数的一个组成部分是：
C_T是转N项的const
k 是我当前正在解决问题的迭代，k-1 是项目的当前位移（解决问题 k-1 的最后一次迭代的结果）。我有一个初始条件 (k=0)。
N是“当前位移（k-1）与优化问题的结果（未来最优位移x^k）x的多少个位置不同”。
如何使 objective 函数的这个分量保持线性？换句话说，如何替换 XOR 运算符？
我考虑过使用绝对差异作为替代方法，但我不确定它是否有帮助。
有线性的方法吗？
我将在 python 中用 PuLP 解决这个问题，也许那里也有可以帮助的东西...
更新：
如果您需要替换的是异或门，那么您可以使用其他线性门的组合来替换它。这是其中的一些 https://en.wikipedia.org/wiki/XOR_gate#Alternatives.
示例：A XOR B = (A OR B) AND (NOT A + NOT B)。当 A 和 B 是二进制时，数学上应转换为：
(A + B - A * B) * ((-A) + (-B) - (-A * -B))
为什么不用乘法？
AND table
0 0 = 0
0 1 = 0
1 0 = 0
1 1 = 1
Multiplication table
0*0 = 0
0*1 = 0
1*0 = 0
1*1 = 1
我认为可以。如果没有，那么我想需要更多细节。
我的记法是：xprev[i] 是以前的解决方案，x[i] 是当前的解决方案。我假设 xprev[i] 是一个二进制常量， x[i] 是一个二进制变量。然后我们可以写
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])
第二行和第三行都可以直接在Pulp中实现。请注意第二行是 'such that'.
下面我们有一条评论声称这是错误的。所以让我们把我的表达式写成B*(1-A)+(1-B)*A。可以构造如下真值table：
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
请注意，A xor B = A*not(B) + not(A)*B 是众所周知的身份。
注意。这里我假设 xprev[i]（或 A）是一个常数，所以事情是线性的。如果两者都是（布尔）变量（我们称它们为 x 和 y），那么我们需要做一些不同的事情。我们可以使用四个不等式将构造 z = x xor y 线性化：
z <= x + y
z >= x - y
z >= y - x
z <= 2 - x - y
现在可以在 MIP 解算器中使用线性。
我的优化问题（我的目标是保持线性）的决策变量是一个放置二进制向量，其中每个位置的值是 0 或 1（项目 i 的两个不同可能位置）。
objective 函数的一个组成部分是：
C_T是转N项的const
k 是我当前正在解决问题的迭代，k-1 是项目的当前位移（解决问题 k-1 的最后一次迭代的结果）。我有一个初始条件 (k=0)。
N是“当前位移（k-1）与优化问题的结果（未来最优位移x^k）x的多少个位置不同”。
如何使 objective 函数的这个分量保持线性？换句话说，如何替换 XOR 运算符？ 我考虑过使用绝对差异作为替代方法，但我不确定它是否有帮助。
有线性的方法吗？
我将在 python 中用 PuLP 解决这个问题，也许那里也有可以帮助的东西...
更新： 如果您需要替换的是异或门，那么您可以使用其他线性门的组合来替换它。这是其中的一些 https://en.wikipedia.org/wiki/XOR_gate#Alternatives.
示例：A XOR B = (A OR B) AND (NOT A + NOT B)。当 A 和 B 是二进制时，数学上应转换为：
(A + B - A * B) * ((-A) + (-B) - (-A * -B))
为什么不用乘法？
AND table
0 0 = 0
0 1 = 0
1 0 = 0
1 1 = 1
Multiplication table
0*0 = 0
0*1 = 0
1*0 = 0
1*1 = 1
我认为可以。如果没有，那么我想需要更多细节。
我的记法是：xprev[i] 是以前的解决方案，x[i] 是当前的解决方案。我假设 xprev[i] 是一个二进制常量， x[i] 是一个二进制变量。然后我们可以写
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])
第二行和第三行都可以直接在Pulp中实现。请注意第二行是 'such that'.
下面我们有一条评论声称这是错误的。所以让我们把我的表达式写成B*(1-A)+(1-B)*A。可以构造如下真值table：
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
请注意，A xor B = A*not(B) + not(A)*B 是众所周知的身份。
注意。这里我假设 xprev[i]（或 A）是一个常数，所以事情是线性的。如果两者都是（布尔）变量（我们称它们为 x 和 y），那么我们需要做一些不同的事情。我们可以使用四个不等式将构造 z = x xor y 线性化：
z <= x + y
z >= x - y
z >= y - x
z <= 2 - x - y
现在可以在 MIP 解算器中使用线性。