What are the efficient ways to improve running time
AnsweredHello,
Please take a look at attached photo. What are the things that I can try to speed up the process. I have everything coded in gurobi-python. Are there things that I can try with Gurobi functions so that the problem can be solved faster?
-
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 Amogh,
if you have everything coded up already, could you share the code here so that we can have a look?
Thanks
Richard
0 -
-
Sure here you go
Data
N = Num_jobs
T = Num_timeslots
K = Num_machines
delta = Num_days
Ck = Cost_using
Co = Cost_overtime
Cu = Cost_undertime
lambdas = mult
SessionLength = SL. #Until this time no overtime
duration = duration.tolist()
l = duration[0:N]
#print(l)
Model starts here
m = Model()
x = {}
z = {}
Q = {}
O = {}
U = {}
for i in range(1,N+1):
for d in range(1,delta+1):
for t in range(1,T+1):
for k in range(1,K+1):
x[(i,d,t,k)] = m.addVar(vtype = GRB.BINARY, name="x%d,%d,%d,%d" % (i,d,t,k))
for i in range(1,N+1):
for d in range(1,delta+1):
for t in range(1,T+1):
for k in range(1,K+1):
z[(i,d,t,k)] = m.addVar(vtype = GRB.BINARY, name="z%d,%d,%d,%d" % (i,d,t,k))
for k in range(1,K+1):
for d in range(1,delta+1):
Q[(k,d)] = m.addVar(vtype = GRB.BINARY, name="Q%d,%d" % (k,d))
for d in range(1,delta+1):
for k in range(1,K+1):
O[(d,k)] = m.addVar(lb = 0, vtype = GRB.CONTINUOUS, name="O%d,%d" % (d,k))
for d in range(1,delta+1):
for k in range(1,K+1):
U[(d,k)] = m.addVar(lb = 0, vtype = GRB.CONTINUOUS, name="U%d,%d" % (d,k))
m.update()
#Job only scheduled if machine is used
for d in range(1,delta+1):
for t in range(1,T+1):
for k in range(1,K+1):
m.addConstr(quicksum(x[(i,d,t,k)] for i in range(1,N+1)) <= Q[(k,d)])
#Job only scheduled if machine is used occupied
for t in range(1,T+1):
m.addConstr(quicksum(quicksum(quicksum(z[(i,d,t,k)] for i in range(1,N+1)) for k in range(1,K+1)) for d in range(1,delta+1)) <=
quicksum(quicksum(Q[(k,d)] for k in range(1,K+1)) for d in range(1,delta+1)))
#overtime
for i in range(1,N+1):
for t in range(1,T+1):
for d in range(1,delta+1):
for k in range(1,K+1):
m.addConstr(t* z[(i,d,t,k)] <= SessionLength + O[(d,k)])
#idletime
for d in range(1,delta+1):
for k in range(1,K+1):
m.addConstr(SessionLength * Q[(k,d)] - quicksum(quicksum(z[(i,d,t,k)] for t in range(1,T+1)) for i in range(1,N+1)) <= U[(d,k)])
#Job starts only once
for i in range(1,N+1):
m.addConstr( quicksum(quicksum(quicksum(x[(i,d,t,k)] for k in range(1,K+1)) for t in range(1,T+1)) for d in range(1,delta+1)) == 1)
#Job cannot start if it can't finish
for i in range(1,N+1):
m.addConstr(quicksum(quicksum(quicksum(x[(i,d,t,k)] for k in range(1,K+1)) for t in range(T+1-l[i-1], T+1)) for d in range(1,delta+1)) == 0)
#Job has allotted enough time slots and starts latest at t = T-l[i]-1
for i in range(1,N+1):
for d in range(1,delta+1):
for k in range(1,K+1):
for t in range(1,(T+1-l[i-1]+1)):
m.addConstr( quicksum(z[(i,d,tbar,k)] for tbar in range(t,(t+1+l[i-1]-1))) >= l[i-1]*x[(i,d,t,k)])
#Job is conducted for l[i] slots
for i in range(1,N+1):
m.addConstr(quicksum(quicksum(quicksum(z[(i,d,t,k)] for k in range(1,K+1)) for t in range(1,T+1)) for d in range(1,delta+1)) == l[i-1])
#Only one Job occupies the slot on a machine
for d in range(1,delta+1):
for t in range(1,T+1):
for k in range(1,K+1):
m.addConstr( quicksum(z[(i,d,t,k)] for i in range(1,N+1)) <= 1)
#symmetry
for d in range(1,delta+1):
for kp in range(1,K+1):
for k in range(1,K+1):
if k < kp:
m.addConstr( Q[(k,d)] >= Q[kp,d])
#Objective
m.setObjective(quicksum(quicksum(O[(d,k)]*Co for k in range(1,K+1)) for d in range(1,delta+1)) +
quicksum(quicksum(U[(d,k)]*Cu for k in range(1,K+1)) for d in range(1,delta+1)) +
quicksum(quicksum(Q[(k,d)]*Ck for k in range(1,K+1)) for d in range(1,delta+1))+
quicksum(quicksum(quicksum(quicksum(lambdas[i-1,d-1,t-1,k-1]*x[(i,d,t,k)] for i in range(1,N+1)) for k in range(1,K+1)) for t in range(1,T+1)) for d in range(1,delta+1)),GRB.MINIMIZE)
m.update()
# m.write("scheduling_model.lp")
# #m.Params.timelimit = 120
# m.setParam('OutputFlag',0)
#cm.setParam('Symmetry',2)0 -
-
It is important to mention that the problem is being solve iteratively. Each iteration, the value of parameter lambda changes in the objective. The model is changed using new setObjective() method. If there is anything I can do in this framework, to speed up, it will be very helpful.
0 -
-
-
Is your time spent in model creation or solution? If it is spent in the model solution, could you post a log of the run so that we can have a look at that?
Regardless, you can always try to use our parameter tuner to find more suitable sets of parameters for your problem. If your problem struggles to find a feasible solution, then it can also be very helpful to inject a feasible start solution (e.g. from a heuristic) into the model.
0 -
-
Hello,
The link you posted doesn't work. I will take a look at parameter tuner for sure.
Here is a screenshot. A question to ask about line 1 (MIP start from previous solve). I wanted to know, after I change the coefficients using m.setObjective(), should this start from previous solve? I am wondering even after I change coefficient in objective function, why is this model starting from previous objective? Or these are 7 solutions to one iteration before I change coefficients which looks like it is.
Next, how do I use parameter tuning? I don't think my model struggles to find feasible solution, I am just concerned with time.
0 -
-
-
- If you change coefficients in your objective function, then the same solution will remain feasible (= not violate any constraints). Therefore it makes total sense that this is the case.
- The Parameter Tuning tool (the link works again, we had issues with our website yesterday) is designed to try out different combinations of parameters to speed up the solution of the problem (not just find feasible solutions). In Python, you can simply run `m.tune()` to get it started (see here). I suggest though that you use an instance that does not take hours to solve, because otherwise the tuner will not be able to give you results quickly.
- You can also try to use a recent feature we developed for multiple scenarios, please see here and for an example here.
0 -
Post is closed for comments.
Comments
7 comments