为什么这两个约束导致我的LP模型在Gurobi中不可行？

LadyDeadpool 发表于 Dev

死侍

我当前在Gurobi的模型不可行或无界，我将其细分为2个约束，这就是造成问题的原因。我有一个安排问题。g [i，j]是二进制变量，表示特定计算机上的序列。（g = 1，如果i在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

一x = 1和一x = 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")

大卫拿

语义上，您的小模型说