Infeasible Result For Double Row Layout Problem

Hi Gurobis Staffs!

I'm currently developing a Double Row Layout Problem using Gurobi Optimizer. With Parameters and constraints below:

n = len(Data[0][:])-1
N = [i for i in range(1,n+1)]
R = [1,2]
l = {(i): Data[0][i] for i in N}
L = sum(l[i] for i in N)
C = {(i,j): Data[i+1][j] for i in N for j in N} #if i<j}
Cobj = {(i,j): Data[i+1][j] for i in N for j in N if i<j}

# arc
arcIJ = [(i,j) for i in N for j in N if i<j]

#%% recommended distance
Rdist = {(i,j): Data[i+(2+n)][j] for i in N for j in N if i<j}

#Data: input from excel data

# 1
model.addConstrs(D[i,j] >= X[i]-X[j] for i in N for j in N if i<j)

# 2
model.addConstrs(D[i,j] >= X[j]-X[i] for i in N for j in N if i<j)

# 3
model.addConstrs(X[j]+((l[i]+l[j])/2) <= X[i]+(L*(1+T[i,j]-U[i,j])) for i in N for j in N if i<j)

# 4
model.addConstrs(X[i]+((l[i]+l[j])/2) <= X[j]+(L*(2-T[i,j]-U[i,j])) for i in N for j in N if i<j)

# 5
model.addConstrs(D[i,j] >= ((l[i]+l[j])/2)*U[i,j] for i in N for j in N if i<j)

# 6
model.addConstr(X[I_argmax] <= X[J_argmin])

# 7
model.addConstrs(D[i,j]-D[j,k]-D[i,k] <= 0 for i in N for j in N for k in N if i < j if i < k if j < k)
model.addConstrs(-D[i,j]+D[j,k]-D[i,k] <= 0 for i in N for j in N for k in N if i < j if i < k if j < k)
model.addConstrs(-D[i,j]-D[j,k]+D[i,k] <= 0 for i in N for j in N for k in N if i < j if i < k if j < k)

# 8
model.addConstrs(U[i,j]+U[j,k]+U[i,k] >= 1 for i in N for j in N for k in N if i < j if i < k if j < k)
model.addConstrs(-U[i,j]+U[j,k]+U[i,k] <= 1 for i in N for j in N for k in N if i < j if i < k if j < k)
model.addConstrs(U[i,j]-U[j,k]+U[i,k] <= 1 for i in N for j in N for k in N if i < j if i < k if j < k)
model.addConstrs(U[i,j]+U[j,k]-U[i,k] <= 1 for i in N for j in N for k in N if i < j if i < k if j < k)

# 9
model.addConstrs((l[i]/2) <= X[i] for i in N)
model.addConstrs(L-(l[i]/2) >= X[i] for i in N)

#10
model.addConstrs(D[i,j] >= Rdist[i,j] for i in N for j in N if i < j)

With those 10 constraints, ive got the result as i expected, but eventually i have to add some constraints that accommodate this ' |X[i] and X[j]| >= Rdist[i,j] ' then i created this new constraint

# Create constraint number 11 => model.addConstrs(abs(X[i]-X[j]) >= Rdist[i,j] for i in N for j in N if i<j)
# with three steps (reference: https://groups.google.com/g/gurobi/c/YUWqUfk3PSc/m/4lAcqJc4BQAJ)
# p = X[i]
# n = X[j]
# M = ? (suitable values, D or Rdist)
# y = binary variable 

#########
#M = D
M = Rdist
NewY = U
# NewY = T
model.addConstrs( X[i] <= M[i,j]*NewY[i,j] for i in N for j in N if i<j)
model.addConstrs( X[j] <= M[i,j]*(1-NewY[i,j]) for i in N for j in N if i<j)
model.addConstrs( X[i] + X[j] >= Rdist[i,j] for i in N for j in N if i<j)

Then, I got the infeasible result, and in my opinion it caused of unsustainable Constraints that i've made. And then i tried using IIS detection with this code:

model.Params.LogToConsole = 1  # enable logging to console
model.Params.OutputFlag = 1  # enable logging to console
model.Params.DualReductions = 0  # disable dual reductions
model.Params.InfUnbdInfo = 1  # enable infeasibility and unboundedness info

if model.status == grb.GRB.INFEASIBLE:
    model.computeIIS()
    print('\nThe following constraints form the infeasible subsystem:')
    for constr in model.getConstrs():
        if constr.IISConstr:
            print(constr.constrName)

And this is the result

Solution count 0
Model is infeasible
Best objective -, best bound -, gap -
Something wrong in DRLP

IIS computed: 2 constraints, 0 bounds
IIS runtime: 0.00 seconds (0.00 work units)

The following constraints form the infeasible subsystem:
R769
R823

Can you help me to figure it out this problems? I've worked for days and still don't have the answers i expected. Thank you

Simranjit Kaur

Gurobi Staff

April 05, 2023 03:02

You can obtain additional information about the constraints R769 and R823 in the IIS by exporting an .ilp format file using

model.write("conflict.ilp")

Enprimarika Nursari

April 05, 2023 04:10

I've already named the constraints one by one, and i got this message

Computing Irreducible Inconsistent Subsystem (IIS)... 
     Constraints          |            Bounds           |  Runtime
      Min       Max     Guess   |   Min       Max     Guess   |
--------------------------------------------------------------------------
        0       931         -         0        81         -           0s
        7         7         -         0         0         -           1s

IIS computed: 7 constraints, 0 bounds
IIS runtime: 0.60 seconds (0.05 work units)

The following constraints form the infeasible subsystem:
CS13[1]
CS13[7]
CS18[3,9]

April 05, 2023 04:12

from this constraint

# 9
model.addConstrs(((l[i]/2) <= X[i] for i in N), name='CS13')
model.addConstrs((L-(l[i]/2) >= X[i] for i in N), name='CS14')

and

M = model.addVars(Cobj, vtype = grb.GRB.CONTINUOUS)
NewY = U
model.addConstrs((X[i] <= M[i,j]*NewY[i,j] for i in N for j in N if i<j), name='CS16')
model.addConstrs((X[j] <= M[i,j]*(1-NewY[i,j]) for i in N for j in N if i<j), name='CS17')
model.addConstrs((X[i] + X[j] >= Rdist[i,j] for i in N for j in N if i<j), name='CS18')

How can i read and solve this infeasibility problem? Thank You.

April 05, 2023 04:34

Thanks, Enprimarika.

It is a good step to name the constraints. However, without knowing the coefficients and the RHS of the constraints in the IIS, it is hard to tell what is leading to the infeasibility.

Could you please execute the following code and share the contents of the conflict.ilp file?

model.optimize()
if model.status == grb.GRB.INFEASIBLE:
    model.computeIIS()
    model.write("conflict.ilp")

- Simran

Infeasible Result For Double Row Layout Problem

Comments

Didn't find what you were looking for?