# Advanced Heuristics for MIP vehicle routing problem in PuLP

I am currently trying to speed up an MIP. An approach I was considering was to implement a cut callback heuristic with PuLP (one which rounds relaxed integer variables greater than .9 to 1). Unfortunately, I do not believe PuLP has such a function to call, and I have looked into the mip module as well as dippy, but I don't feel like jumping to those. So, as a side note, if anyone knows how this can be done natively with PuLP let me know...

This leads me to my main question. Since PuLP is a wrapper and can be used with other solvers, I did see that Gurobi has such a function, and was able to call the code to Gurobi from PuLP with the code below:

Lp_prob = plp.LpProblem('Problem', plp.LpMinimize)
sd = plp.solvers.GUROBI(mip=True)
sd.actualSolve(Lp_prob, callback=mycallback)


Here is the function I am trying to call:

def mycallback(model, where):
model._vars = model.getVars()
if where == GRB.Callback.MIPNODE:
for x in model._vars:
if model.cbGetNodeRel(x) > 0.9 and model.cbGetNodeRel(x) < 1.0:
model.cbSetSolution(x, 1.0)
else:
return


However, after running a couple of times, the heuristic doesn't quite speed things up, in fact it kind of slows it down. I was wondering if this was implemented correctly, or if I were missing something. Any help or suggestions would be greatly appreciated.

• Also move the model._vars = model.getVars() into the if-condition, the callback function gets called very often and should be designed as resource efficient as possible, because it can considerable slow down the solve process. – user3680510 Apr 10 '20 at 23:24

It is difficult to tell from this information. You need the examine the logs of the solver if your primal bound (how good are the solutions) or dual bound (how good is the relaxation) is not moving as fast as you wish it would be.

I would try to run this heuristic not at every node, but maybe at every 50 (the correct value of this needs to be benchmarked) or so.

You can use something like this for it:

if model.cbGet(GRB.Callback.MIP_NODCNT) % 50 == 0


I would also evaluate how good this heuristic is, by for example printing the objective value of the suggested solutions and seeing how often it is better than what gurobi found. If this is not often the case than you need to design probably a better heuristic.

• Hey, so I tried all of the changes you recommended and it still ends up being very slow... I looked and saw that cbSetSolution wasn't actually setting the variable it seems. Would you recommend another way of implementing this? Progress on this seem to be at a standstill at the moment. – ctyler9 Apr 12 '20 at 21:05
• As stated this is very difficult without knowing the problem. I just saw that there is also the method cbUseSolution(), which you can call immediately after you have set all variables and it returns the new objective value, you can also query the current best incumbent objective value and compare it. This makes it easy to compare the objective values. So what is evaluation of the stuff i wrote above? Are the solutions not good enough or is the bound not good enough? Does your heuristic produce often better solution? – user3680510 Apr 13 '20 at 13:07