linear-programming - 如何在线性规划问题中将多个变量相乘？

Question

我试图将问题表述为整数线性规划问题。

对于 [1,n] 中的 i，我有二进制变量 x[i] 和 y[i]，它们的值被限制为 0 或 1。

我想做以下约束： sum(x[i] * y[i] for i in array) <= 100

我希望能够将 x[i] 和 y[i] 相乘，但这会变成一个二次方程（非线性）。

有什么办法可以做到这一点吗？我对线性编程很陌生，所以我非常感谢任何帮助！

标签： linear-programming

Answer 1

先说一点理论。我们可以线性化

z = x*y

对于二进制变量 x,y,z通过：

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

在您的具体情况下，我们可以如下应用：

sum(i, z[i]) <= 100 
z[i] >= x[i] + y[i] - 1

其中z[i]是一个额外的二进制变量。我们不需要 <= 约束z[i] <= x[i], z[i] <= y[i]。我们可以放松z[i]到 0 到 1 之间的连续值，这有时对性能有所帮助。

请注意，二元变量的存在不再使其成为 LP，而是成为 MIP 模型。