Почему эти два ограничения делают мою модель LP невозможной в Gurobi? - PullRequest
Новая
       13

Почему эти два ограничения делают мою модель LP невозможной в Gurobi?

1 голос
/ 09 июня 2019

Моя текущая модель в Gurobi неосуществима или неограничена, и я разбил ее на 2 ограничения, которые вызывают проблему. У меня есть проблема с расписанием. g [i, j] - двоичная переменная, которая указывает последовательность на определенной машине. (g = 1, если я продолжаю до j. x [i, r] - двоичная переменная присваивания (x =, если i назначен машине r.)

Несократимая подсистема (IIS) показывает эти три ограничения, и когда я удаляю ограничение секунд, модель работает, но все переменные g остаются равными 0, а это не то, что мне нужно 

for i in packages: 
        model.addConstr(quicksum(x[i, r] for r in machines) == 1)

for i in packages
        for j in packages:
            if i != j:
                for r in machines:
                    model.addConstr(g[i, j] + g[j, i] >= x[i, r] + x[j, r] - 1) 

    for i in packages:
            for j in packages:
                if i != j:
                    for r in machines:
                    model.addConstr(g[i, j] + g[j, i] <= (x[i, r] + x[j, r]) / 2)

Я действительно не вижу проблемы с этими ограничениями: оба x равны 0: 

g[i, j] + g[j, i] >= -1 
g[i, j] + g[j, i] <= 0

один х = 1 и один х = 0: 

g[i, j] + g[j, i] >= 0 
g[i, j] + g[j, i] <= 0.5

оба x = 1: 

g[i, j] + g[j, i] >= 1 
g[i, j] + g[j, i] <= 1

Кто-нибудь знает, почему это делает модель невозможной? Как я описал, я не могу найти здесь никаких нарушений.

РЕДАКТИРОВАТЬ это мой файл ilp: 

Subject To
 _first_constraint: x_1_NRML-1-1 + x_1_NRML-1-2 + x_1_NRML-1-3 = 1
 _first_constraint: x_2_NRML-1-1 + x_2_NRML-1-2 + x_2_NRML-1-3 = 1
 _first_constraint: x_3_NRML-1-1 + x_3_NRML-1-2 + x_3_NRML-1-3 = 1
 _first_constraint: x_4_NRML-1-1 + x_4_NRML-1-2 + x_4_NRML-1-3 = 1
 seconds_constraint: - x_1_NRML-1-1 - x_2_NRML-1-1 + g_1_2 + g_2_1 >= -1
 seconds_constraint: - x_1_NRML-1-1 - x_3_NRML-1-1 + g_1_3 + g_3_1 >= -1
 seconds_constraint: - x_1_NRML-1-2 - x_3_NRML-1-2 + g_1_3 + g_3_1 >= -1
 seconds_constraint: - x_1_NRML-1-2 - x_4_NRML-1-2 + g_1_4 + g_4_1 >= -1
 seconds_constraint: - x_1_NRML-1-2 - x_2_NRML-1-2 + g_1_2 + g_2_1 >= -1
 seconds_constraint: - x_1_NRML-1-3 - x_2_NRML-1-3 + g_1_2 + g_2_1 >= -1
 seconds_constraint: - x_2_NRML-1-2 - x_3_NRML-1-2 + g_2_3 + g_3_2 >= -1
 seconds_constraint: - x_2_NRML-1-3 - x_3_NRML-1-3 + g_2_3 + g_3_2 >= -1
 seconds_constraint: - x_2_NRML-1-3 - x_4_NRML-1-3 + g_2_4 + g_4_2 >= -1
 seconds_constraint: - x_1_NRML-1-3 - x_3_NRML-1-3 + g_1_3 + g_3_1 >= -1
 seconds_constraint: - x_2_NRML-1-1 - x_3_NRML-1-1 + g_2_3 + g_3_2 >= -1
 seconds_constraint: - x_1_NRML-1-1 - x_4_NRML-1-1 + g_1_4 + g_4_1 >= -1
 seconds_constraint: - x_1_NRML-1-3 - x_4_NRML-1-3 + g_1_4 + g_4_1 >= -1
 seconds_constraint: - x_2_NRML-1-1 - x_4_NRML-1-1 + g_2_4 + g_4_2 >= -1
 seconds_constraint: - x_2_NRML-1-2 - x_4_NRML-1-2 + g_2_4 + g_4_2 >= -1
 seconds_constraint: - x_3_NRML-1-1 - x_4_NRML-1-1 + g_3_4 + g_4_3 >= -1
 seconds_constraint: - x_3_NRML-1-2 - x_4_NRML-1-2 + g_3_4 + g_4_3 >= -1
 seconds_constraint: - x_3_NRML-1-3 - x_4_NRML-1-3 + g_3_4 + g_4_3 >= -1
 third_constraint: - 0.5 x_1_NRML-1-3 - 0.5 x_2_NRML-1-3 + g_1_2 + g_2_1
   <= 0
 third_constraint: - 0.5 x_1_NRML-1-1 - 0.5 x_3_NRML-1-1 + g_1_3 + g_3_1
   <= 0
 third_constraint: - 0.5 x_1_NRML-1-2 - 0.5 x_3_NRML-1-2 + g_1_3 + g_3_1
   <= 0
 third_constraint: - 0.5 x_1_NRML-1-3 - 0.5 x_4_NRML-1-3 + g_1_4 + g_4_1
   <= 0
 third_constraint: - 0.5 x_1_NRML-1-1 - 0.5 x_2_NRML-1-1 + g_1_2 + g_2_1
   <= 0
 third_constraint: - 0.5 x_2_NRML-1-1 - 0.5 x_3_NRML-1-1 + g_2_3 + g_3_2
   <= 0
 third_constraint: - 0.5 x_2_NRML-1-3 - 0.5 x_3_NRML-1-3 + g_2_3 + g_3_2
   <= 0
 third_constraint: - 0.5 x_2_NRML-1-1 - 0.5 x_4_NRML-1-1 + g_2_4 + g_4_2
   <= 0
 third_constraint: - 0.5 x_2_NRML-1-2 - 0.5 x_4_NRML-1-2 + g_2_4 + g_4_2
   <= 0
 third_constraint: - 0.5 x_3_NRML-1-2 - 0.5 x_4_NRML-1-2 + g_3_4 + g_4_3
   <= 0
 third_constraint: - 0.5 x_1_NRML-1-1 - 0.5 x_4_NRML-1-1 + g_1_4 + g_4_1
   <= 0
 third_constraint: - 0.5 x_3_NRML-1-3 - 0.5 x_4_NRML-1-3 + g_3_4 + g_4_3
   <= 0
Bounds
Binaries
 x_1_NRML-1-1 x_1_NRML-1-2 x_1_NRML-1-3 x_2_NRML-1-1 x_2_NRML-1-2
 x_2_NRML-1-3 x_3_NRML-1-1 x_3_NRML-1-2 x_3_NRML-1-3 x_4_NRML-1-1
 x_4_NRML-1-2 x_4_NRML-1-3 g_1_2 g_1_3 g_1_4 g_2_1 g_2_3 g_2_4 g_3_1 g_3_2
 g_3_4 g_4_1 g_4_2 g_4_3
End

Я попробовал это с относительно небольшим количеством. У меня есть пакеты 1,2,3,4 и машины NRML-1-1, NRML-1-2 и NRML-1-3.

Вот mcve: 

from gurobipy import *

model = Model("mcve")

M = 60000
packages = [1, 2, 3, 4]
machines = [1, 2, 3]

h_ = {}
for i in machines:
    h_[i] = 20

print(packages)
print(machines)
print(h_)


x = {}
for i in packages:
    for r in machines:
        x[i, r] = model.addVar(lb=0, obj=0, vtype=GRB.BINARY, name="x_" + str(i) + "_" + str(r))

g = {}
for i in packages:
    for j in packages:
        g[i, j] = model.addVar(lb=0, obj=0, vtype=GRB.BINARY, name="g_" + str(i) + "_" + str(j))

T__ = {}
for i in packages:
    T__[i] = model.addVar(lb=0, obj=0, vtype=GRB.CONTINUOUS)

Ttotal = {}
Ttotal = model.addVar(lb=-1e30, obj=1, vtype=GRB.CONTINUOUS)

model.modelSense = GRB.MAXIMIZE
model.update()
# Add Constraints

for i in packages:
    model.addConstr(quicksum(x[i, r] for r in machines) == 1, name=' first constraint')

for i in packages:
    for j in packages:
        if i != j:
            for r in machines:
                model.addConstr(g[i, j] + g[j, i] >= x[i, r] + x[j, r] - 1, name='second constraint')

for i in packages:
    for j in packages:
        if i != j:
            for r in machines:
                model.addConstr(g[i, j] + g[j, i] <= (x[i, r] + x[j, r]) / 2, name = 'third constraint')

for i in packages:
    for j in packages:
        if i != j:
            model.addConstr(T__[i] <= T__[j] - quicksum(x[i, r] * h_[r] for r in machines) + M * (1 - g[i, j]), name='Zusammenhang T__ und g1')
           # model.addConstr(T__[j] <= T__[i] - quicksum(x_[j, r] * h_[r].total_seconds() for r in workstation) + M * g[i, j], name='Zusammenhang T__ und g2')

for i in packages:
    model.addConstr(Ttotal <= T__[i] + quicksum(x[i, r] * h_[r] for r in machines))


model.optimize()
model.computeIIS()
model.write("model.ilp")

1 Ответ

0 голосов
/ 10 июня 2019

Семантически, ваша маленькая модель говорит

  • first_constraint: Назначьте 4 упаковки на 3 машины (ровно по одной машине на каждую упаковку)
  • второе ограничение: если пакеты i, j находятся на одной машине, g [i, j] + g [j, i] должно быть 1
  • третье ограничение: если на любой машине нет обоих пакетов i и j, то g [i, j] и g [j, i] должны быть равны 0.

Вместе они делают невозможным размещение двух пакетов на одном компьютере, поскольку оба они будут находиться на одном компьютере, а также ни на одном из других.

Похоже, что для третьего ограничения вы хотите сказать, что g [i, j] должно быть 0, если не существует машины, имеющей оба пакета i и j.

...