DARP: How to correctly calculate the Big-M value that exists in two inequalities?
Answered
The formulation includes a Big-M . Actually I am not sure of how to calculate it perfectly. I am sharing my calculations hereafter. This Big-M does exist in two inequalities. I can share the inequalities and relevant data if it really may result in a mess.
K = [1,2]
M = 2500
ek = {1:0.0, 2:0}
lk = {1: 2000, 2:2000}
d1= {m+10: 0 for m in range(12)}
d = {0:0, 1:15,2:30,3:15,4:30,5:15,6:30,7:15,8:30,9:0,**d1}
c = {(i,j): np.round(np.hypot(xc[i]-xc[j], yc[i]-yc[j])) for i in N for j in N } # equlidian distances
t = {a : np.round (c[a] / v) for a in c }# time between nodes --velocity 60km/h
B = m.addVars(N ,vtype=GRB.CONTINUOUS)
Bk = m.addVars(K, vtype=GRB.CONTINUOUS)
D = m.addVars(N ,vtype=GRB.CONTINUOUS)
m.addConstrs((B[j] >= B[i] + d[i] + t[i,j] - M*(1- quicksum(xijk[k,i,j] for k in K)) for (i,j) in A), '10')
m.addConstrs ((D[j] >= D[i] + d[i]+t[i,j] -M*(1-quicksum(xijk[k,i,j] for k in K)) for (i,j) in A), '14')
This is how I isolated M :
Bk[k] + t[0,j] -B[j] + = > M
D[i] + d[i]+t[i,j] -D[j] => M
My struggle in calculating M is due to the variable for first equation I chose the biggest Bk[k] and t[0,j] and smallest B[j]
For the second equation I chose biggest D[i] + d[i]+t[i,j] and smallest D[j].
I then picked the biggest M of both. But it gave me infeasible model after 10 seconds from the runtime. I increased the value of M gradually until the model is run again.
I can elaborate more if required.
-
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?. -
-
-
Dear Sabreen,
Could you elaborate more on how exactly you were able to isolate the big M? I am just wondering why you only have \(\texttt{t[0,j]}\) in the first inequality, while in your constraints named \(\texttt{'10'}\), you consider different \(\texttt{t[i,j]}\) w.r.t. \(\texttt{i}\). Is it possible that you forgot to add \(\texttt{d[i]}\) in the first inequality, as you have a \(\texttt{+}\) sign but no term after that? It also appears in the constraints named \(\texttt{'10'}\) and thus, should be considered when calculating the big M. Also, in the first inequality, you use \(\texttt{Bk}\) but I don't see any \(\texttt{Bk}\) in your constraints.
By how much did you have to increase your M? Could you provide the bounds on the variables/scalars \(\texttt{Bk, t, B, D, d}\)?
Best regards,
Jaromił1 -
-
Many many thanks Jaromil, you always support me. I am preparing the required data. Will come soon.
Regards,
Sabreen
0 -
-
Dear Jaromil,
hereafter are the perfect constraints that include the Big-M.
I succeeded to calculate the bounds of the variables but failed to get the values of the D variable.
If you can help me get it, it will be appreciated.
D is actually a part of the time dictionary t. The t dictionary is indexed in (i,j) for any i, j, but D is indexed by (0,j) only. I want to get all the values of all the indeces (0,j)........ I tried to extract a dictionary D from a dictionary t but failed.
c = {(i,j): np.round(np.hypot(xc[i]-xc[j], yc[i]-yc[j])) for i in N for j in N }
t = {a : np.round (c[a] / v) for a in c }# distance over velocity 60km/hm.addConstrs((B[j] >= Bk[k] + t[0,j] - M*(1-xijk[k,0,j]) for j in N for k in K), '9')
m.addConstrs((B[j] >= B[i] + d[i] + t[i,j] - M*(1- quicksum(xijk[k,i,j] for k in K)) for i in N for j in N), '10')
m.addConstrs((B[j] >= B[i] + t[i,j] - M*(1- z[i,j]) for r in R for i in Cr[r] for j in Cr[r]), '11')
m.addConstrs ((D[j] >= D[i] + d[i]+t[i,j] -M*(1-quicksum(xijk[k,i,j] for k in K)) for i in N for j in N), '14')The bounds are as follows:
max min t [i,j] 824 0 B 1745 50 Bk 2000 0 d 30 15 D ???
0 -
-
-
Dear Sabreen,
You're welcome. Thank you for the kind words.
You can access the \(\texttt{(0,j)}\) indices of the \(\texttt{t}\) dictionary via \(\texttt{t[0,j]}\) as you already did in the first constraint. To get the max and min values of \(\texttt{D}\), you could use the below code.
DminVal = float('inf')
DmaxVal = float('-inf')
for j in N:
if t[0,j] < DminVal:
DminVal = t[0,j]
if t[0,j] > DmaxVal:
DmaxVal = t[0,j]
print("D min value:"+str(DminVal))
print("D max value:"+str(DmaxVal))To extract a dictionary \(\texttt{D}\) from \(\texttt{t}\), you could use
D = {}
for j in N:
D[j] = t[0,j]
print(D)Best regards,
Jaromił1 -
-
Dear Jaromil,
Now I got all the bounds:
max min t[I,j] 824 0 B 1745 50 Bk 2000 0 d 30 15 D 529 0
I isolated M for each constraint, in order as follows:
M Bk[k] + t[0,j] - B[j] << M 2000 +529-50 2479 B[i] + d[i] + t[i,j]-B[j] << M 1745+30+824-50 2549 B[i] + t[i,j]-B[j] << M 1745+824-50 2519 D[i] + d[i]+t[i,j]-D[j] << M 529+30+824-0 1383 So M now should be greater than 2549, right?
Best regards,
Sabreen
0 -
-
-
Dear Sabreen,
Yes, an M of 2549 should be sufficient. I would most likely go for a slightly larger M of 3000 just to be sure. Note that while it is often recommended to take the smallest value for M to avoid numerical issues, in theory the M should be as large as possible. Since your M is not too large, it should be safe to go with a slightly larger value of 3000 in this case.
Best regards,
Jaromił1 -
-
Dear Jaromil,
That is great. I have got your idea Jaromil and will use M = 3000.
With my best wishes,
Sabreen
1 -
Post is closed for comments.
Comments
8 comments