Is there any method to reduce cpu time in callback function ?
Answered
Hi
I am trying to use Branch and cut method to solve a vehicle routing problem. When there is a relaxed continuous solution obtained, a specified condition will be checked and a user-defined cut will be added at the current node. My callback function is shown as follows.
def EPI(model, where):
if where == GRB.Callback.MIPNODE: #
# nodecnt = int(model.cbGet(GRB.callback.MIPNODE_NODCNT))
status = model.cbGet(GRB.Callback.MIPNODE_STATUS) #
if status == GRB.OPTIMAL:
sol = model.cbGetNodeRel(model._vars) # A relaxed sol. obtained at the explored node
SubFun = model._Gfun
N = model._coeff[0]
K = model._coeff[1]
NN=0
for i in range(K*(N**2)):
if 1>sol[i]>0:
NN+=1
if NN==0:
# inte_sol+=1
model._num_inte_sol+=1
if NN > 2*N:
cut = np.zeros((K, N ** 2))
Z = np.zeros(K)
label_cut = np.zeros((K, N ** 2))
# sorted_cut = np.zeros((K, N ** 2))
pi = np.zeros((K, N ** 2))
for i in range(K):
# for j in range(N ** 2):
cut[i, :] = sol[i * (N ** 2) : (i+1) * (N ** 2)]
for i in range(K):
Z[i] = sol[i + K * (N ** 2)]
# Indeices of relaxed sol in descending order (max-min).
for i in range(K):
label_cut[i, :] = np.argsort(-cut[i, :])
# label_cut.astype(int)
for i in range(K):
for j in range(N ** 2):
pi[i, j] = SubFun[int(label_cut[i, j])]
# # EPIs construction
# for i in range(K):
# if np.dot(pi[i, :], cut[i, :]) + 1e-4 > Z[i]:
# model.cbCut(
# sum((pi[i, j] * model._vars[j + i * (N ** 2)]) for j in range(N ** 2)) <= model._vars[
# i + K * (N ** 2)])
# model._numEPI += 1
# EPIs construction
if sum(np.dot(pi[i, :], cut[i, :]) for i in range(K) )+ 1e-4 > sum((Z[i])for i in range(K)):
model.cbCut( sum((pi[i, j] * model._vars[j + i * (N ** 2)]) for i in range(K) for j in range(N ** 2)) <= sum((model._vars[
i + K * (N ** 2)] )for i in range(K) ) )
model._numEPI += 1
# print(pi)
As the log file shows, a lot of time is wasted in calling the callback function. I want to know is there any functions can be used to reduce time in user-callback.
Cutting planes:
User: 1
Gomory: 11
Projected implied bound: 1
MIR: 7
Flow cover: 36
Zero half: 11
RLT: 17
Explored 932319 nodes (15297759 simplex iterations) in 589.02 seconds
Thread count was 4 (of 4 available processors)
Solution count 10: 2541.27 2541.36 2543.87 ... 2562.47
Optimal solution found (tolerance 1.00e-04)
Best objective 2.541265089671e+03, best bound 2.541265089671e+03, gap 0.0000%
User-callback calls 1894330, time in user-callback 362.67 sec
Best
Canqi Yao
-
Official comment
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 Canqi Yao,
Your callback has been called 1894330 times for a total of 362.67 seconds. This makes it roughly to 0.19 milliseconds per callback, which is not too much. What you could try is to reduce the number of values which you have to re-calculate and pre-calculate them outside of the callback.
If the values ofN = model._coeff[0]
K = model._coeff[1]are fixed, then you could pre-calculate most of the objects and values you use in the callback and then acces them, e.g., via
model._someValue
Best regards,
Jaromił0 -
Hi Jaromił
Apart from reducing time in callback function, can we decrease the number of calling callback function by choosing some nodes with callback function added?
Best
Canqi
0 -
Hi Canqi,
You cannot directly choose the nodes where the callback is being called or not being called, as the callback \(\texttt{MIPNODE}\) is always called whenever a mip node is explored within the B&B algorithm.
You could implement a counter, and only compute a cut at every n-th call. You could also check the MIPNODE_NODCNT and only compute a cut whenever this value has some specific properties, e.g., is a multiple of 2 or similar.
Best regards,
Jaromił0
Post is closed for comments.
Comments
4 comments