Skip to main content

NLP "Network Loading Problem" infeasible Error

Answered
Bruno Senese
  • Gurobi-versary
  • First Comment
  • First Question

Hello Gurobi community,

I'm new in Gurobi and I'm trying to model a NLP and i'm getting an infeasible answer for Gurobi.

I used the model.write(".ilp") and gave me the answer of where is the infeasibility (Constraint #5.2).

I'm trying to update that constraint in many different ways to get it feasible, but no luck.

Would you guys/girls help me in this one!?

Thanks in advance.

Below is where i'm getting the error.

=======================================================

###The .ilp File error###

\ Model CNLP_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize

Subject To
Rest52[MAO,1]: <= -1
Bounds
End

========================================================
#My formulation

LHS ={(i,k): (quicksum(quicksum(f[i,j,k,t] for j in N for i,j in A)
- quicksum(f[l,i,k,t] for l in N for l,i in A)) for t in T) for i in N for k in K} #5.2
vrp.addConstrs((LHS[i,k] == (1 if i==O[k] else (-1 if i==D[k] else 0)) for i in N for k in K), "Rest52")

======================================================================

0

Comments

7 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Eli Towle
    • Gurobi Staff
    Edited

    Hi Bruno,

    The IIS contains a single constraint with no variables on the left-hand side ( \( 0 \leq -1 \) ). This suggests that something is wrong with the expression you use to generate the \( \texttt{LHS} \) dictionary.

    I think the problem is with the expressions created by the inner \( \texttt{quicksum} \) functions:

    quicksum(f[i,j,k,t] for j in N for i,j in A)

    This does not create the summation \( \sum_{j \in N \colon (i, j) \in A} f_{ij}^{kt} \). Rather, it is equivalent to \( |N| \sum_{(i,j) \in A} f_{ij}^{kt}, \) because you iterate over all elements of the \( A \) set \( |N| \) times. The second inner \( \texttt{quicksum} \) statement is doing virtually the same thing, so these two expressions cancel each other out.

    Instead, you can just swap the second \( \texttt{for} \) with an \( \texttt{if} \):

    quicksum(f[i,j,k,t] for j in N if i,j in A)

    Better yet, if you created the \( f \) variables using Model.addVars(), and if \( j \in N \) for all \( (i, j) \in A \), you could take advantage of the tupledict class and simply write:

    f.sum(i,'*',k,t)

    Eli

    1
  • Bruno Senese
    Edited
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Eli, thank you for the quick and accurate answer.

    I think you pointed me in the right path, but unfortunately i still didn't make it work.

    Would you mind to look the code with the changes and tell me what i did wrong.?

    Below is the formulation and the code (if it helps to understand, I added a picture with the problem made in AMPL too).

    I apologise in advance for all the "bad formulations"that you will find. I'm still a begginer in Gurobi and python.

    Thank you for the attention given.

    ========================================================================

    from gurobipy import *
    import numpy as np

    n = 16
    T = ["Truck","Carreta"] #Acfts = set T - Conjunto de tipos de veículos disponíveis

    N = [1,2,3,4,5,6,7,8,9,10,11,12] #set V - Conjunto de nós da Rede
    U = {"Truck":12000,"Carreta":24000} #param U {t in T}, >= 0 - Capacidade da acft do tipo t.

    c = {"Truck":1.00,"Carreta":1.40} #param c {t in T}, >= 0 - Custo por Km da acft do tipo t.

    #A = [[11,14],[11,1],[14,1],[14,2],[14,13],[1,2],[15,14],[15,1],[10,14]]

    K, R, O, D = multidict({
    1:[12000,1,2],
    2:[5000,15,2],
    3:[10000,15,13],
    4:[12000,10,13],
    5:[4000,11,2]})

    A, Dist = multidict({(11,14):336,(11,1):765,(14,1):573,(14,2):989,(14,13):985,(1,2):414,(15,14):511,(15,1):820,(10,14):100})

    cnlp = Model("CNLP")

    x = cnlp.addVars(A, T,lb=0,ub=GRB.INFINITY,vtype=GRB.INTEGER,name="ArcsEVeic") #5.4
    f = cnlp.addVars(A, K, T,vtype=GRB.BINARY,name="Rota")

    Total = quicksum(quicksum(Dist[i,j]*c[t]*x[i,j,t] for i,j in A) for t in T) #5.1

    cnlp.setObjective(Total,GRB.MINIMIZE)

    #LHS ={(i,k): (quicksum(f.sum(i,'*',k,t) - f.sum(l,'*',k,t)) for t in T) for i in N for k in K} #5.2
    #vrp.addConstrs((LHS[i,k] == (1 if i==O[k] else (-1 if i==D[k] else 0)) for i in N for k in K), "Rest52")  #it didn't work

    LHS ={(i,k): (quicksum(quicksum(f[i,j,k,t] for j in N if i,j in A)
    - quicksum(f[l,i,k,t] for l in N if l,i in A)) for t in T) for i in N for k in K} #5.2
    vrp.addConstrs((LHS[i,k] == (1 if i==O[k] else (-1 if i==D[k] else 0)) for i in N for k in K), "Rest52") #is giving me an error.

    LHS53 = {(i,j,t): quicksum(R[k]*f[i,j,k,t] for k in K) for i,j in A for t in T} #5.3
    RHS53 = {(i,j,t): (U[t]*x[i,j,t]) for i,j in A for t in T} #5.3
    cnlp.addConstrs(((LHS53[i,j,t] <= RHS53[i,j,t]) for i,j in A for t in T), "Constr53") #5.3

    cnlp.addConstrs(((x[i,j,t] >=0) for i,j in A for t in T), "Constr54") #5.4

    cnlp.addConstrs(((f[i,j,k,t] <= 1) for i,j in A for k in K for t in T),"Constr55") #5.5

    LHS56 = {(i,j,k): quicksum(f[i,j,k,t] for t in T) for i,j in A for k in K} #5.6
    RHS56 = {(i,j,k): quicksum(x[i,j,t] for t in T) for i,j in A for k in K} #5.6
    cnlp.addConstrs(((LHS56[i,j,k] <= RHS56[i,j,k]) for i,j in A for k in K), "Constr56") #5.6

    cnlp.addConstrs(((R[k]*f[i,j,k,t] <= U[t]) for i,j in A for k in K for t in T), "Constr57") # 5.7

    cnlp.addConstrs(((quicksum(f[i,j,k,t] for t in T) <= 1) for i,j in A for k in K), "Constr58") #5.8

    cnlp.computeIIS()
    cnlp.write("NLPm.mps")
    cnlp.write("NLPr.rew")
    cnlp.write("NLPl.lp")
    cnlp.write("NLPrl.rlp")
    cnlp.write("NLPi.ilp")
    #cnlp.write("NLPs.sol")
    #cnlp.write("NLPms.mst")
    cnlp.write("NLPh.hnt")
    #cnlp.write("NLPb.bas")
    cnlp.write("NLPp.prm")
    cnlp.write("NLPa.attr")
    cnlp.write("NLPj.json")

     

    cnlp.Params.TimeLimit = 120 # seconds
    if cnlp.status == GRB.INFEASIBLE:
    cnlp.feasRelaxS(0, False, False, True)
    cnlp.optimize()
    #cnlp.printAttr('f')
    cnlp.printAttr('x')

    0
  • Eli Towle
    • Gurobi Staff

    Hi Bruno,

    What exactly is the error you are getting? You might need to add parentheses around the indices in the \( \texttt{LHS} \) construction where you check if \( (i,j) \in A \) and \( (\ell, i) \in A \). E.g.:

    LHS = {(i,k): (quicksum(quicksum(f[i,j,k,t] for j in N if (i,j) in A) - quicksum(f[l,i,k,t] for l in N if (l,i) in A)) for t in T) for i in N for k in K}

    In the next line, you make a call to \( \texttt{vrp.addConstrs()} \), but I guess this should be \( \texttt{cnlp.addConstrs()} \). \( \texttt{vrp} \) is never defined anywhere.

    Thanks,

    Eli

    0
  • Bruno Senese
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Eli,

    So, I tried in all the ways you showed me, but I'm still getting that the model is infeasible.

    Even with the parenthesis.

    I tried both ways. With the quicksum and with the f.sum, both gives me an infeasibility.

    #cnlp.addConstrs(((quicksum(f.sum(i,'*',k,t) - f.sum('*',i,k,t)) for t in T) == (1 if i==O[k] else (-1 if i==D[k] else 0)) for i in N for k in K), "Rest52")

    LHS = {(i,k): (quicksum(quicksum(f[i,j,k,t] for j in N if (i,j) in A) - quicksum(f[l,i,k,t] for l in N if (l,i) in A)) for t in T) for i in N for k in K} #5.2

    cnlp.addConstrs((LHS[i,k] == (1 if i==O[k] else (-1 if i==D[k] else 0)) for i in N for k in K), "Rest52")

    If i uses the relaxation module, it runs with all wrong values, but runs.

    #if cnlp.status == GRB.INFEASIBLE:
    # cnlp.feasRelaxS(0, False, False, True)

    Also, if i run without the Constraint 5.2. Gives me a result of 0, but at least is feasible. Witch gives me the indication that the constraint 5.2 is the faulty one.

    I feel that is just a small detail that we are missing to make it feasible.

    Btw, the cnlp an vrp was only a typo when i was transcriptin to the text.

    Thanks,

    Bruno.

    0
  • Eli Towle
    • Gurobi Staff
    Edited

    Hi Bruno,

    Maybe this is the problem: the \( \texttt{for t in T} \) should be inside of the \( \texttt{quicksum()} \) function when you define \( \texttt{LHS} \). I.e.:

    LHS = {(i,k): (quicksum(f.sum(i,'*',k,t) - f.sum('*',i,k,t) for t in T)) for i in N for k in K}

    Could you try changing this?

    Thanks,
    Eli

    0
  • Bruno Senese
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Eli,

    Thank you very much or the time and effort in helping me!

    You nailed it! You found the error and now is feasible!

    I worked the entire week to find this error, redoing the formulas and maths, and in the end it was just a pair of Brackets!! LOL.

    Thank you again!

    Bruno.

    0

Post is closed for comments.

Didn't find what you were looking for?

New post