在 Gurobi 中添加二进制变量

Question

所以我想在i和j之间的距离小于或等于150和[=16时z[i, j] = 1添加一个二进制变量z =] 否则。我有一个列表 c，其中每个 c[i][j] 代表 i 和 j 之间的距离。下面我当然不能把z设置成一个普通的二进制变量：

y = m.addVars(I, J, vtype=GRB.BINARY, name="assign")

我想添加约束：

# One day mailing
m.addConstrs(
    z[i,j] <= y[i,j] for i in I for j in J,
    "Serve")

# Coverage Constraint
m.addConstr(
   quicksum(h[i] * z[i, j] for i in I for j in J) <= 
        0.9 * quicksum(h[i] * y[i, j] for i in I for j in J),
        "Cover")

其中 h 是一个整数列表。如何设置 z?

Answer 1

首先你需要添加z作为二进制变量：

z = m.addVars(I, J, vtype=GRB.BINARY, name="z")

然后你需要约束来确保z[i, j] = 1当且仅当c[i, j] <= 150。一种方法是使用指标约束：

z = 1 -> c <= 150
z = 0 -> c >= 150

这相当于

c > 150 -> z = 0
c < 150 -> z = 1

您按如下方式添加：

m.addConstrs((z[i, j] == 1) >> (c[i][j] <= 150) for i in I for j in J)
m.addConstrs((z[i, j] == 0) >> (c[i][j] >= 150) for i in I for j in J)

您也可以自己明确建模：如果 c[i][j] - 150 的值有上限和下限 M 和 m（即所有 i, j 的 M >= c[i][j] - 150 >= m），您可以使用以下约束:

M * (1-z) >= c - 150
m * z <= c - 150

如果c > 150，两个不等式的右边都是正的。第一个然后强制 1 - z = 1，因此 z = 0。第二个不等式将很容易得到满足。

如果c < 150，右边是负数。第一个不等式变得微不足道，而第二个不等式则迫使 z = 1.

对于 M，c 中的最大输入即可，对于 m，如果所有 c[i][j] 均为非负数，则您可以选择 -150。

您按如下方式添加这些约束：

m.addConstrs( M * (1 - z[i, j]) >= c[i][j] - 150 for i in I for j in J )
m.addConstrs( m * z[i,j] <= c[i][j] - 150 for i in I for j in J )

请注意，我忽略了 c = 150 的情况。这是因为对于浮点数，等式总是只被认为在公差范围内得到满足，因此没有简单的方法来区分严格和非严格的不等式。您可以用 epsilon 来近似，例如：

z = 0 -> c >= 150 + epsilon

在 Gurobi 中添加二进制变量

Adding binary variable in Gurobi

python

linear-programming

gurobi

integer-programming