Skip to main content

Performing condition constraints

Ongoing

Comments

10 comments

  • Eli Towle
    Gurobi Staff Gurobi Staff

    Let \( I \) be your set of demands and \( J \) your set of facility locations. It sounds like you want the following constraints:

    $$\begin{align}D_{ij} &\leq x_j \quad \forall i \in I,\ j \in J.\end{align}$$

    Consider a fixed \( j \in J \). If \( x_j = 0 \), then the above constraints force \( D_{ij} = 0 \) for all \( i \in I \), as desired. If \( x_j = 1 \), then we have \( D_{ij} \leq 1 \) for all \( i \in I \), meaning any (or all) demands can be assigned to location \( j \).

    This requires \( |I| \cdot |J| \) constraints. You can add all of these constraints using \( \texttt{for} \) loops:

    for i in demandpoint:
        for j in Candidatepoint:
    m.addConstr(D[i, j] <= x[j], name=f'limit_demand[{i},{j}]')

    Alternatively, you can add these constraints with a single call to Model.addConstrs():

    m.addConstrs((D[i, j] <= x[j] for i in demandpoint for j in Candidatepoint), name='limit_demand')
    0
  • chaung yun chi
    Gurobi-versary
    Curious
    Conversationalist

    Thanks for your help!

    But I have one more question

    If I want to build a constraint

    Σdij' *disDCij’ ≤ disDCij + M (1-Xj)        j,j'∈ J       

    Which I want to express that :

    "all demands are assigned to the closest facility"   

    but I don't know how to write

    j' 

    properly, so this is what I tried

    for i in demandpoint:
    for j1 in Candidatepoint:
    if j!=j1:
    m.addConstrs((D[i,j1]*disDC[i,j1]
    <=disDC[i,j]+M*x[j] for j in Candidatepoint), name="4")


    Although it doesn't show any error and the problem is solved, but I still wonder if it's the correct way

    to do it? Or does it really express what I trying to do?

     

     

    and in case you're wondering,

    disDC is a dictionary contains distance between demand and candidate point

    disDC={}
    for i in range(1,11):
    for j in range(1,41):
    s1=math.sqrt(((demand[i])[0]-(Candidate[j])[0])**2+((demand[i])[1]-(Candidate[j])[1])**2)
    disDC.setdefault((demandpoint[i-1],Candidatepoint[j-1]),s1)

    demand and Candidate are two dictionaries contains the coordinates of each nodes.

    demandpoint and Candidate are two lists of indexes of the dictionaries.

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    I would guess you want the following constraints (where \( s \) is shorthand for \( disDC \)):

    $$\begin{align}s_{ij} d_{ij} &\leq s_{ik} + (s_{ij} - s_{ik})*(1 - x_k) \enspace \forall i \in I,\ j \in J,\ k \in J: s_{ij} > s_{ik}.\end{align}$$

    Consider a fixed \( i \in I \) and \( j \in J \). If \( d_{ij} = 0 \), we aren't assigning demand \( i \) to facility \( j \), and the above constraints are satisfied for any \( k \in J \). If \( d_{ij} = 1 \), then it must hold that \( x_k = 0 \) for all \( k \in J \) satisfying \( s_{ij} > s_{ik} \). In other words, there is no open facility that is closer to demand \( i \) than location \( j \).

    Below is an example code snippet. Your Python code isn't far from this.

    for i in demandpoint:
        for j in Candidatepoint:
            for k in Candidatepoint:
                M = disDC[i, j] - disDC[i, k]
                if M > 0:
                    m.addConstr(disDC[i, j]*D[i, j] <= disDC[i, k] + M*(1 - x[j]),
    name=f'closest_facility[{i},{j},{k}]')

    Depending on the size of \(I\) and \(J\), this approach may require adding a very large number of constraints to the model. I've seen facility location problems that instead minimize the total demand assignment distance in the objective function. Perhaps you could leave off these constraints and incorporate \( \sum_{i \in I} \sum_{j \in J} s_{ij} d_{ij} \) into the objective function.

    0
  • chaung yun chi
    Gurobi-versary
    Curious
    Conversationalist

    You're right, I 've already put that in my objective function at that time, but some how I thought it was a good idea to make few constraints describing same stuff  haha. I delete the constraints and it's fine now.

    And is there any way I can generate a picture with my answer?

    or a list of it?

    I tried matplotlib but I don't know how to select those dots with the value 1, and abandon others.

    Is there a function calls only the variables which equals '1' of the integer variables?

    I want to make a map alike picture to visualize my result.

    0
  • chaung yun chi
    Gurobi-versary
    Curious
    Conversationalist

    I got the '1' value variables, but I can't call the data based on it.

    for v in m.getVars():
    if v.x==1:
    print('%s %g' % (v.varName, v.x))
    d[1,4] 1
    d[2,18] 1
    d[3,22] 1
    d[4,10] 1
    d[5,34] 1
    d[6,5] 1
    d[7,5] 1
    d[8,19] 1
    d[9,12] 1
    d[10,18] 1
    f[5,4] 1
    f[10,4] 1
    f[12,4] 1
    f[18,4] 1
    f[19,4] 1
    f[22,4] 1
    f[34,4] 1
    X[5] 1
    X[10] 1
    X[12] 1
    X[18] 1
    X[19] 1
    X[22] 1
    X[34] 1
    Launch or not[4] 1

    This what I tried(I write it after  m.optimize())

    for i in Candidatepoint:
    if x[i]==1:
    plt.plot((coorC[i])[0],(coorC[i])[1],"ro")

    and I got

    GurobiError: Constraint has no bool value (are you trying "lb <= expr <= ub"?)

     

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    Exactly what lists are you trying to create? If you want a list of all demand assignments, you could use something like:

    dassign = [k for k, v in D.items() if v.X > 0.5]

    This creates the following list:

    [(1, 4), (2, 18), (3, 22), (4, 10), (5, 34), (6, 5), (7, 5), (8, 19), (9, 12), (10, 18)]

    After optimizing, you can retrieve a variable's value at the current solution by querying the X attribute of the corresponding Var object. This is why you receive an error with the code \( \texttt{if x[i] == 1} \) (but \( \texttt{if x[i].X == 1} \) will work).

    0
  • chaung yun chi
    Gurobi-versary
    Curious
    Conversationalist

    Thanks, now I can use matplotlib to visualize my result.

    But what I was trying to do is a "Hierarchical facility problem" which the result is different from mine.

    https://drive.google.com/file/d/1E3xaUioLMS5zUef3gP9wcdNAB32aRabT/view?usp=sharing 

    The demand I circled are assigned to facilities relatively far, so I should add more constraints to make sure they all assigned to the closest facility, or modify my objective function?

     

     m.setObjective(quicksum(L[k]*CL for k in Candidatepoint)
    +quicksum(x[j]*CR for j in Candidatepoint)
    +quicksum(D[i,j]*disDC[i,j] for i in demandpoint for j in Candidatepoint)*Cs
    +quicksum(disCC[j,k]*F[j,k]for j in Candidatepoint for k in Candidatepoint)*Cs,
    GRB.MINIMIZE)
    #Building Launch station
    CL=30000

    #Building Recharge station
    CR=300

    #unit cost per distance
    Cs=100

    #vehicle endurance
    E=35

    I've tried several different method of objective function, but the results are getting worse.

    I think I have put all the constraints I can put in this situation, but I'm most likely wrong.

    #only one kind of facility is build in a place
    for j in Candidatepoint:
    m.addConstr((L[j]+x[j])<=1,name="one kind")


    #each demand is assigned once
    for i in demandpoint:
    m.addConstr(quicksum(D[i,j] for j in Candidatepoint)==1, name="5")

    #assign recharge station to launch station only if it's build
    for j in Candidatepoint:
    m.addConstr(quicksum(F[j,k]for k in Candidatepoint)==x[j] ,name="once")



    #launch station is only available when it's build
    m.addConstrs((F[j,k] <= L[k] for j in Candidatepoint for k in Candidatepoint),name="585")

    #Recharge station can't be assigned to itself
    for j in Candidatepoint:
    m.addConstr(F[j,j]==0,name="no")

    #demands are only assigned to facilities which are build
    m.addConstrs((D[i, j] <= x[j]+L[j]for i in demandpoint for j in Candidatepoint), name='limit')

    #at least one recharge station exist
    m.addConstr(quicksum(x[j] for j in Candidatepoint)>=1, name="999")

    #at least one launch station exist
    m.addConstr(quicksum(L[j] for j in Candidatepoint)>=1, name="789")



    #the distance between Recharge station and Launch station does not exceed endurance of vehicles
    for j in Candidatepoint:
    for k in Candidatepoint:
    m.addConstr(disCC[j,k]*x[j]*L[k]<=E,name="117")


    #the distance between facilities and demands does not exceed endurance of vehicles
    for i in demandpoint:
    for j in Candidatepoint:
    m.addConstr(D[i,j]*disDC[i,j]<= E, name="2")
    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    It's hard to say what's wrong without knowing exactly how everything is defined. Can you post a full working version of your code (including the Matplotlib code)?

    0
  • chaung yun chi
    Gurobi-versary
    Curious
    Conversationalist

    Can I have your email ?

    I think it's kind of complicated to describe the whole thing here.

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    This discussion is continued in another forum post.

    0

Please sign in to leave a comment.