Performing condition constraints
OngoingHi
I want to generate a few constraints to represent that
"if a facility is built in location j then you can assign demand i there
otherwise, you can't assign demand i there"
which can also simplify to: "You can only assign demand to facilities which exist"
My variables:
x[j]=1 if facility is built in location j =0 otherwise
D[i,j]=1 if demand i is assigned to facility j =0 otherwise
D=m.addVars(demandpoint,Candidatepoint,vtype=GRB.BINARY,name = "d")
x=m.addVars(Candidatepoint,vtype=GRB.BINARY,name="X")
How can I use addConstr to do this?
I've tried
m.addConstr(quicksum(D[i,j] for i in demandpoint)-quicksum(D[i,j]*(1-x[j]) for j in Candidatepoint)>=0,name="98")
but the results are not what I want, which D[i.j] is correct, but x[i,j] are all zeros and it supposed to be some 1s.
Optimal solution found (tolerance 1.00e-04)
Best objective 9.264424414624e+03, best bound 9.264424414624e+03, gap 0.0000%
d[1,1] 0
d[1,2] 0
d[1,3] 0
d[1,4] 0
d[1,5] 0
d[1,6] 0
d[1,7] 1
... (Edited for ease of viewing)
X[32] 0
X[33] -0
X[34] -0
X[35] -0
X[36] 0
X[37] 0
X[38] 0
X[39] -0
X[40] 0
I've searched the topics describing how to use big M constraint to model a if- else situation in linear programming, but I'm not sure if it's the same situation, and I don't really understand their techniques there.
-
Official comment
-
Gurobi Staff
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?. -
-
-
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 -
-
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 -
-
-
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 -
-
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 -
-
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] 1This 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 -
-
-
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 -
-
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=35I'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 -
-
-
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 -
-
Can I have your email ?
I think it's kind of complicated to describe the whole thing here.
0 -
-
-
This discussion is continued in another forum post.
0 -
Post is closed for comments.
Comments
11 comments