如何在线性规划问题中乘以多个变量？
How to multiply multiple variables in a linear programming problem?
我试图将问题表述为整数线性规划问题。
我在 [1,n] 中有二进制变量 x[i] 和 y[i]，它们的值被限制为 0 或 1。
我想做如下约束：
sum(x[i] * y[i] for i in array) <= 100
我希望能够将 x[i] 和 y[i] 相乘，但这变成了二次方程（非线性）。
有什么办法可以做到这一点吗？我对线性规划还很陌生，所以非常感谢任何帮助！！
首先是一些理论。我们可以线性化
z = x*y
对于 二进制变量 x,y,z by:
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 模型。
我试图将问题表述为整数线性规划问题。
我在 [1,n] 中有二进制变量 x[i] 和 y[i]，它们的值被限制为 0 或 1。
我想做如下约束： sum(x[i] * y[i] for i in array) <= 100
我希望能够将 x[i] 和 y[i] 相乘，但这变成了二次方程（非线性）。
有什么办法可以做到这一点吗？我对线性规划还很陌生，所以非常感谢任何帮助！！
首先是一些理论。我们可以线性化
z = x*y
对于 二进制变量 x,y,z by:
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 模型。