Skip to main content

Help with constraints

Awaiting user input

Comments

7 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.
  • Eli Towle
    • Gurobi Staff

    The following constraints look suspicious to me:

    R163: C[8,1] + C[8,2] + C[8,3] + C[8,4] + C[8,5] + C[8,6] = 1
    GC42: C[8,1] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753
    GC43: C[8,2] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753
    GC44: C[8,3] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753
    GC45: C[8,4] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753
    GC46: C[8,5] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753
    GC47: C[8,6] = 1 -> TL[8] - 394.510693580372 TL_temp[8]
     = 2.124630242822753

    By \(\texttt{R163}\), exactly one of the binary variables \(\texttt{C[8,1]}\), \(\texttt{C[8,2]}\), \(\texttt{C[8,3]}\), \(\texttt{C[8,4]}\), \(\texttt{C[8,5]}\), and \(\texttt{C[8,6]}\) must equal \( 1 \). However, no matter which of these binary variables equals one, constraints \(\texttt{GC42}\) through \(\texttt{GC47}\) enforce the exact same constraint:

    TL[8] - 394.510693580372 TL_temp[8] = 2.124630242822753

    In your Python code, these indicator constraints are built as follows:

    for i in range(1,P+1):
        for k in range(1,M+1):
            m.addConstr((C[i,k]==1)>> (TL[i]==(r_d[i]*d[i]/CU[i] + a_d[i]*TL_temp[i])))

    Should the constraints enforced by these indicator constraints have some dependency on \(\texttt{k}\)?

    1
  • ramesh singh
    • Gurobi-versary
    • First Comment
    • First Question

    Thank you!

            m.addConstr((C[i,k]==1)>> (TL[i]==(r_d[i]*d[i]/CU[i] + a_d[i]*TL_temp[i])))

    this constraints have indirect dependency on k, through TL_temp[i]  (m.addConstr(TL_temp[i]==(sum(bw[i,k]*C[i,k] for k in range(1,M+1)))) 

    to make direct dependency this TL_temp[i] can be replaced with bw[i,k]. will this solve the problem?  shall i also replace TL_temp[i] in TR constraints?, will it not affect the TL_temp constraints?  Previous constraints    m.addConstr(TL_temp[i]==(sum(bw[i,k]*C[i,k] for k in range(1,M+1))))   this assign the value of C[i,k]=1 for which k it has highest bandwidth (bw). 

     

    0
  • Eli Towle
    • Gurobi Staff

    I can't say if those changes are valid, as I'm not familiar with your application. That said, maybe it would help to understand why there exists no feasible solution with \(\texttt{T1[8]}=3.54706\) and \(\texttt{D[8]}=0\). To do this, let's fix \(\texttt{T1[8]}\) to \(3.54706\) and \(\texttt{D[8]}\) to \(0\) and see where the infeasibility comes from.

    First, consider the constraint \(\texttt{qc1}\):

    qc1: - TL[8] + T1[8] + [ TL[8] * D[8] - TR[8] * D[8] ] = 0

    With \(\texttt{T1[8]}\) and \(\texttt{D[8]}\) fixed to \(3.54706\) and \(0\) respectively, this constraint yields \(\texttt{TL[8]} = 3.54706\).

    Next, recall constraints \(\texttt{R163}\) and \(\texttt{GC42}\) through \(\texttt{GC47}\) that we discussed previously. Together, these constraints enforce the following relationship:

    TL[8] = 2.124630242822753 + 394.510693580372 TL_temp[8]

    Finally, let's examine the following set of constraints:

    R42: bw[8,1] = 0.00360555127692798
    R43: bw[8,2] = 0.0280713376904728
    R44: bw[8,3] = 0.0481663782303384
    R45: bw[8,4] = 0.0502195170419178
    R46: bw[8,5] = 0.0064031242328657
    R47: bw[8,6] = 0.0547083182247194
    R163: C[8,1] + C[8,2] + C[8,3] + C[8,4] + C[8,5] + C[8,6] = 1
    qc0: TL_temp[8] + [ - C[8,1] * bw[8,1] - C[8,2] * bw[8,2]
    - C[8,3] * bw[8,3] - C[8,4] * bw[8,4] - C[8,5] * bw[8,5]
    - C[8,6] * bw[8,6] ] = 0

    Together, these constraints tell us that \(\texttt{TL_temp[8]}\) must equal one of the following values:

    0.00360555127692798
    0.0280713376904728
    0.0481663782303384
    0.0502195170419178
    0.0064031242328657
    0.0547083182247194

    Given the relationship \(\texttt{TL[8]} = 2.124630242822753 + 394.510693580372 \cdot \texttt{TL_temp[8]}\), it follows that \(\texttt{TL[8]}\) must equal one of the following values:

    3.547058777823206
    13.199073144820016
    21.126781525728084
    21.936766742301057
    4.650731225011888
    23.70764681027251

    This contradicts our conclusion that \(\texttt{TL[8]}\) equals \(3.54706\). The first value is very close, but it differs by ~1.22e-6, which is enough for Gurobi to reasonably claim that the model is infeasible.

    Looking at your data, my best guess for the source of the infeasibility is the \(\texttt{bw_initial}\) and \(\texttt{latency_mec_host}\) arrays. All of the values included in those arrays are truncated to the sixth decimal point, which can easily cause calculation errors on the order of 1e-6 or higher.

    0
  • ramesh singh
    • Gurobi-versary
    • First Comment
    • First Question

    okay thank you so much for detaild explainations

    0
  • ramesh singh
    • Gurobi-versary
    • First Comment
    • First Question

    if i removed TL_temp constraints 

    and update the 

    TL and TR as 

    for i in range(1,P+1):
            m.addConstr(TL[i]==sum((raw_data[i]*delta[i]/CU[i] + action_data[i]*bw[i,k])*C[i,k] for k in      range(1,M+1))) #optimize
     
    for i in range(1,P+1):
    m.addConstr(TR[i]==sum((raw_data[i]*bw[i,k]+ raw_data[i] *delta1[k]/ CM[k])*C[i,k] for k in range(1,M+1))) 
    Further, i truncate bw_initial and latency_bw_host upto 12 decimal points. still having same problem... 
     
    0
  • Eli Towle
    • Gurobi Staff

    I would try computing an irreducible infeasible subsystem (IIS) by calling Model.computeIIS() after optimizing. Then, write out an ILP model file and inspect it:

    m.computeIIS()
    m.write("model.ilp")

    The ILP file will contain a subset of constraints and bounds that together form an infeasible system. However, this infeasible system can be made feasible by removing any single constraint or bound. This should give you a good idea of why the model is still infeasible.

    See the article How do I determine why my model is infeasible? for more information.

    0

Post is closed for comments.