My Code takes too long time : how I perform Arc elimination to make it faster
AnsweredMy code aims at optimizing a NP-hard network problem. The network composes of 22 nodes and 484 arcs.
I used v = m.getVars() & print(len(v)) to get the number of variables are 2986. However, when I used constrs = m.getConstrs() & print(len(constrs)) I get 0 constraints ( I do not why ? may be something in my formulation).
The GOOD NEWS is my code is working but takes tooooo long time the elapsed time reached 9 hours for 19 % gap.
My main question:
I want to make Arc elimination for Strengthening the mathematical model
How to formulate/code "arc elimination". This is because many arcs are infeasible and if I removed them before the optimization order a lot of time can be saved.
I have a number of nodes (N) classified as pickup nodes (P), dropoff nodes (D), transfer nodes (C), and depot nodes.
The nodes are called i (for origin nodes) and j (for destination nodes). In each constraint, I specify which nodes ( which i or j the constraint should consider). The image below shows an example of two constraints.
I have a list of arcs that should be removed
For instance,
Some arcs connected to depot nodes can always be eliminated. These are the following:
– No arc can go to the node representing the origin depot, i.e., all arcs(i,0) are
infeasible for i ∈N.
– No arc can go from the node representing the destination depot, i.e., all arcs(2n+
1,i)are infeasible for i ∈N.
– No arc can go from the origin depot to a drop-off node i, i.e., all arcs(0,n+i)are
infeasible for i ∈P.
– No arc can go from a pick-up node i to the destination depot, i.e., all arcs(i,2n+1)
are infeasible for i ∈P
Very Urgently, How to program a code to remove such arcs?
Thanks in Advance,
Sabreen Hassan
-
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?. -
-
-
Hi Sabreen,
Try calling Model.update() before getting the constraints and variables. This should resolve the issue.
I see two possibilities of how to remove the infeasible arcs. First, you can try to not introduce these arcs at all, meaning that you could implement additional if-statements to not add these specific arcs. A different approach would be to use the Model.remove() function to remove the specific variables and constraints.
Best regards,
Jaromił1 -
-
Thanks a lot, Jaromił Najman. the Model.update() worked well and my model composes of 2986 variables and 1686 constraints.
I am going to figure out how to use if-statement -as per your recommendation- to perform Arc Elimination.
Thanks again,
Best Regards,
Sabreen
0 -
-
I have applied some Arc Elimination rules in the hope to get the model solved faster, but unfortunately, it gets slower. I compared the basic model and the model with arc elimination for a gap of 48%.
The basic model reached a gap of 48% within 52 minutes. Unexpectedly, with the arc elimination strategy, the model get slower, and passed 75 minutes and didn't reach a gap of 48%
Here are what I have done:1. I created a list for all arcs
2. I created lists of all possible infeasible arcs and combined them in one list
3. I created a new list called A for feasible arcs only.
4. I applied this in the model
# all Arcs
A0 = [(i,j) for i in N for j in N if j!=0 and i!=j and i!=2*n+1]
infeasible_arc1 = [(0,n+i) for i in P]
infeasible_arc2 = [(i,2*n+1) for i in P]
infeasible_arc3 = [(n+i, i) for i in P]
infeasible_arc4 = [(i, j ) for i in PD for j in PD if e[i] + d[i] + t[i,j] > l[j]]
infeasible_arc5 = [(i, j ) for i in P for j in N if t[i,j] + d[j] + t[j,n+i] > L[i]]
infeasible_arc6 = [(j,n+i ) for i in P for j in N if t[i,j] + d[j] + t[j,n+i] > L[i]]
infeasible_arc7 = [(i,n+j) for i in P for j in P if e[j]+d[j]+t[j,i]+d[i]+t[i,j+n]+ d[j+n]+ t[n+j, n+i]>l[i+n] ]
infeasible_arc8 = [(i,n+i) for i in P for j in P if e[i] +d[i]+t[i,n+i]+d[n+i]+ t[n+i,j]+d[j]+ t[j, n+j]> l[n+j]]
# all infeasible arcs
A00 = infeasible_arc1 + infeasible_arc2 + infeasible_arc3 + infeasible_arc4 + infeasible_arc5 + infeasible_arc6 +infeasible_arc7 + infeasible_arc8
# all feasible arcs
A = [a for a in A0 if a not in A00]1- I changed the variables accordingly( for example
xijk = m.addVars(K,N,N, vtype= GRB.BINARY)
to
xijk = m.addVars(K,A, vtype= GRB.BINARY)
2- Changed the objective function also
m.setObjective(quicksum(c[i,j]*xijk[k,i,j] for i in N for j in N for k in K),GRB.MINIMIZE)
to
m.setObjective(quicksum(c[i,j]*xijk[k,i,j] for i,j in A for k in K),GRB.MINIMIZE)
3- changed my constraints (for example)
m.addConstrs((quicksum(xijk[k,j,i]-xijk[k,i,j] for j in N) == 0 for i in PDC for k in K),'4')
to
m.addConstrs((quicksum(xijk[k,j,i]-xijk[k,i,j] for j in N if (i,j) in A and (j,i) in A ) == 0 for i in PDC for k in K),'4')
I do not know why the model is delayed, is it due to some mistakes ?! or the way of how I implemented the arc elimination let the model needs more calculations and hence more time.
Notes:
Any arc (i,j) not in A is infeasible.
# Basic lists of the model
R = [1,2,3,4] # Requests
K = [1,2] # list of cars
P = [1,2,3,4] #Pick-up nodes
D = [5,6,7,8] # drop-off nodes,
PD = P + D
C = [10,11,12,13,14,15,16,17,18,19,20,21] # all transfer nodes
PDC = PD + C
Cr = {1: C[0:3], 2 : C[3:6],3: C[6:9], 4: C[9:12] }
O = [0,9]
N = O + P + D + C
OC = O + C0 -
-
-
Dear Sabreen,
It is not guaranteed that the infeasible arc formulation provides any speed-up.
Could you write your model to an LP file by executing the Model.write("myLP.lp") function and inspect whether the problem you are actually building is correct? It would be best, if you reduce the size of your problem such that you can comprehend the model and detect possible mistakes when it is in its LP file form.You could also print the feasible and infeasible arc lists and check whether all arcs in the lists are correct.
Best regards,
Jaromił0 -
-
Dear Jaromil,
Thanks a lot for your support. I will find how to understand that .lp file to analyze it correctly. For now, I think I have to return a step back to the basic model. I discovered an issue with it. When I run the code it quickly starts and reaches a 30% gap at a very acceptable time, but then it starts to slow done until it reaches a 25.6% gap and runs for long hours without changing this gap.
Any idea of what is happening and how I should react?
An additional issue, the CTRL-C command to interrupt the running code does not work with me. This part of Gurobi manual.
Regards,
Sabreen
0 -
-
-
Dear Sabreen,
You could have a look at our documentation of Model File Formats.
There may be many answers to the behavior you see. You could try experimenting with some of the most important parameters to see whether you can improve the optimization process. Analyzing smaller models first can be helpful.
Usually, hitting CTRL-C once and waiting should interrupt your solution process. Hitting CTRL-C once may sometimes not work directly, you could try hitting it twice or three times quickly one after the other.
Best regards,
Jaromił0 -
-
Dear Jaromil,
I have some good news. My basic model is working perfectly now and so is the Arc-elimination-based model. with arc elimination I realized higher speed reaching a gap of 8% within 600 seconds as compared to a 51% gap within the same period for the basic model.
I am going to take a further step with more strategies to strengthen my model, this will help me with a bigger size model with more variables added in the future.
Of course, I will need your help and everybody her in the community, will come soon with more questions :)
0 -
-
-
Dear Sabreen,
Great to hear that your model is making such a good progress!
The community is here to help you with future questions :)
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
9 comments