Does adding callbacks (lazy constraints) affect the heuristics?
Hi,
In the context of my research, I am developing a model needing lazy constraints. These lazy constraints are needed to add Benders cuts to my problem.
However, when doing so, I have the feeling that my model struggles to find good quality solutions. I know that lazy constraints turn off some presolve techniques, so I did all experiments without the presolve.
To investigate, I tried to solve the initial problem (without any decomposition) with a dummy callback that never adds lazy constraints. And when doing so, I do not get the same results. Out of the very few experiments I ran, it seems the model with dummy lazy constraints finds fewer good quality solutions.
That's why I wonder if the presence of lazy constraints callbacks has an impact on other techniques than presolve, for example heuristics?
From a high point of view, this makes sense : in the presence of lazy constraints, you may want to put less effort in heuristics since solutions can be rejected by the lazy constraints.
However, in my case, the lazy constraints only affects the “quality” of a solution : the same solution with updated theta (theta being the value of the subproblem in the decomposition) is valid. Consequently, if lazy constraints impact heuristics, is there a way to tell the solver “My lazy constraints will not reject your solutions, so you can ignore them in heuristics parameters”?
Finally, is it also possible to know if other callbacks (user cuts and heuristics) have impacts on important components of the solver, other than the presolve? I will have to implement user cuts in my context and knowing this can help me choosing better the solver parameters.
Thanks in advance for your answers!
-
Linked to my previous post, I have another question.
Is there a way in a lazy constraint callback to “re-push” a new solution? In my context, the MIP master problem may find solutions using heuristics. These “pending” solutions are of the form (theta, u) where u contains integer variables and needs to check if lazy constraints are satisfied.
When a lazy constraint callback is called, only the theta may be incorrect in the solution (it comes from a Benders decomposition). However, I noticed that, once lazy constraints added, these solutions are discarded and not used by the model. In other words, there is no way to update the theta and use the updated solution.
In my case, it would be very interesting to push the valid solution with updated theta as a valid primal solution of my master problem. This will enable to take advantage of the efforts made by heuristics to build valid solutions.
An alternative would be to create heuristics computing true values of theta myself. However, I doubt I will be able to create heuristics as effective as those in Gurobi.
0 -
Please sign in to leave a comment.
Comments
1 comment