Leveraging Gurobi Callbacks to Incorporate Expensive Heuristics into Optimization
Answered
I am seeking guidance on effectively utilizing Gurobi's callback functionality to integrate computationally expensive heuristics into my optimization process. My objective function involves minimizing f(x,y)+g(x), where g(x) is the computationally intensive component. Given the computational cost associated with evaluating g(x), I aim to precompute its value using a heuristic method outside of the optimization loop and subsequently incorporate this value into the optimization process using Gurobi callbacks.
To this end, I have attempted to modify the objective function to minimize f(x,y)+z, where z is a new decision variable representing the precomputed value of g(x). I am using Gurobi's Model.cbSetSolution() method within a callback function to update the value of with the heuristic result.
Below is the code snippet of my callback implementation:
def mycallback(model, where):
if where == GRB.Callback.MIPNODE:
if model.cbGet(GRB.Callback.MIPNODE_STATUS) == GRB.OPTIMAL:
x_val = model.cbGetNodeRel(x)
new_z_val = myheuristic(x_val)
z_var = model.getVarByName("z")
model.cbSetSolution(z_var,new_z_val)
objval = model.cbUseSolution()
print("Objective used:", objval)
mdl.optimize(mycallback)
However, despite implementing this approach, the objective value obtained from the updated solution is consistently set to 1e+100. I have also experimented with using GRB.Callback.MIPSOL instead of GRB.Callback.MIPNODE, but the results remain unchanged.
Since the variable z is only used in the objective function the new solution doesn't cause any infeasibility. As far as I understand the reason could be because of no improved solution is found which is normal in my case. Because the optimization process always sets the z to 0 and by assigning the new value to the z, (extracted from my heuristic) the objective function will be worse.
I am seeking recommendations on how to effectively integrate the precomputed heuristic values into my optimization process. Should I continue refining my current approach with modifications, or should I consider an alternative strategy?
Thank you for your assistance.
-
Hi Mohammad,
I think it would be a good idea to closely read the API doc for cbSetSolution.
When you use
model.cbSetSolution(z_var,new_z_val)
You are telling the solver you have a new solution, and that z_var = new_z_val, but this is then only a partial solution consisting of 1 variable - and Gurobi must try and complete the solution, which involves solving your model with fixed z. Unless this solve is trivial then Gurobi would almost certainly abandon trying to complete the solution and ignore your attempt.
However, I think the larger issue here is that this approach does not do what you want it to. I will explain it with a simpler example: minimize x, x >= 0, x is integer
Solver: "I have a solution of x = 0"
Callback: "Ok, now I have calculated that x should equal 2, so I will give you a solution with x = 2"
Solver: "I have accepted your solution. But x=0 is better, so I will now ignore your solution".The problem you are trying to solve might be better approached with gurobi-machinelearning where you first train a ML model to approximate g(x) - either with your data provided by your heuristic, or the data that the heuristic was trying to approximate - then embed the trained model in the optimization model. There would be no use of callbacks in this approach.
- Riley
1 -
Hi Riley
Thank you for your thorough explanation, and I appreciated how you simplified the answer :). It appears I may have overestimated the callback, so I'll explore alternative approaches, particularly the one you suggested.
Regards
-M
1
Please sign in to leave a comment.
Comments
2 comments