Is there any method to reduce cpu time in callback function ?
AnsweredHi
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 userdefined 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 (maxmin).
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, :]) + 1e4 > 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) )+ 1e4 > 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 usercallback.
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.00e04)
Best objective 2.541265089671e+03, best bound 2.541265089671e+03, gap 0.0000%
Usercallback calls 1894330, time in usercallback 362.67 sec
Best
Canqi Yao

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 recalculate and precalculate them outside of the callback.
If the values ofN = model._coeff[0]
K = model._coeff[1]are fixed, then you could precalculate most of the objects and values you use in the callback and then acces them, e.g., via
model._someValue
Best regards,
Jaromił 
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 nth 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ł
Please sign in to leave a comment.
Comments
3 comments