My current model in Gurobi is infeasible or unbounded and I broke it down to 2 constraints, which are causing the problem. I have a scheduling Problem. g[i,j] is the binary variable, which indicates the sequence on a certain machine. (g = 1, if i is proceed before j. x[i,r] is a binary assignment variable (x= if i is assigned to machine r.)
The Irreducible Inconsistent Subsystem (IIS) is showing these three constraints and when I am removing the seconds constraint, the model is working, but all g variables are staying 0, which is not what I want
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)
I really don't see the problem with these constraints: both x are 0:
g[i, j] + g[j, i] >= -1
g[i, j] + g[j, i] <= 0
one x = 1 and one x = 0:
g[i, j] + g[j, i] >= 0
g[i, j] + g[j, i] <= 0.5
both x = 1:
g[i, j] + g[j, i] >= 1
g[i, j] + g[j, i] <= 1
Does anyone know, why this is causing the model to be infeasible? Like I described, I can't find any violations here.
EDIT this is my ilp file:
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
I tried it with a relative small amount. I have packages 1,2,3,4 and machines NRML-1-1, NRML-1-2 and NRML-1-3.
Here is a 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")
Semantically, your small model says
Together they make it impossible for two packages to be on the same machine, since they would both be on one machine and also both not be on any any of the others.
It looks like for the third constraint, you are intending to say g[i, j] must be 0 unless there exists a machine does have both packages i and j.