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

Question

我当前在 Gurobi 中的模型是不可行的或无界的，我将其分解为 2 个约束，这导致了问题。我有一个调度问题。 g[i,j]是二进制变量，表示在某台机器上的序列。（g = 1，如果 i 在 j 之前进行。 x[i,r] 是一个二进制赋值变量（x= 如果 i 被分配给机器 r。）

Irreducible Inconsistent Subsystem (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")

Answer 1

在语义上，你的小模型说

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。

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

Why are these two constraints causing my LP model to be infeasible in Gurobi?

python

gurobi