Блог

Итак, я хочу добавить двоичную переменную, z где z[i, j] = 1 , когда расстояние между i и j меньше или равно 150 и z[i, j] = 0 в противном случае. У меня есть список, 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 ?

Сначала вам нужно добавить 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)
  

Вы также можете смоделировать это самостоятельно явно:
Если у вас есть верхняя и нижняя границы M и m для значения c[i][j] - 150 (т.е. M >= c[i][j] - 150 >= m для всех i, j ), вы можете использовать следующие ограничения:

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

Если c > 150 , то правые части обоих неравенств будут положительными. Затем первая вызывает 1 - z = 1 и, следовательно z = 0 . Второе неравенство будет тривиально выполнено.

Если c < 150 , то правые стороны отрицательны. Первое неравенство становится тривиальным, в то время как второе вызывает z = 1 .

Для M максимальной записи в c будет достаточно, поскольку m вы можете выбрать, -150 если все c[i][j] значения неотрицательны.

Вы добавляете эти ограничения следующим образом:

 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