Multiple callbacks question
AnsweredI want to know if I can create a MIPSOL callback routine like the one below.
Where MIPSOL:
- Add a lazy constraint to the model,
- Check if the incumbent solution is still feasible,
- If feasible: get the solution via cbGetSolution,
- Use that solution in a heuristic to further improve the solution.
Looks like I cannot do all of this in a single callback. But then, is there a way to achieve this using multiple callbacks in Gurobi?
Regards
Buddi
-
Hi Buddi,
I am a bit confused by this approach. When you add a lazy constraint in the MIPSOL callback, you usually first get the newly found incumbent solution and try to cut it off through a lazy constraints as is done in, e.g., the tsp.py example. Thus, you would know whether the newly found incumbent has been cut off or not because you have to deduce a lazy constraint to cut it off. Unless you are adding lazy constraints without any knowledge about the incumbent solution, but then how do you guarantee that you add the correct lazy constraint? Could you please elaborate a bit more?
Best regards,
Jaromił0 -
Hello Jaromil,
For example, let us say we have an electric bus routing problem with the charging schedule. So we have the trip timetable that is given. We need to find the minimum number of buses that can serve these trips, the minimum battery size for the buses, and the charging schedule. Let us say that the charging location is fixed. If I remove the continuity constraints (i.e., consecutive arcs must be served by the same bus), I get a speedy solution for even relatively big problems. So let us say I want to do something like this;
- I first try to check if I can find a feasible solution that satisfies all constraints except the continuity constraints,
- When I find such an incumbent, I check against the continuity constraints.
So far, this works, and I also observe some solution time improvement. But I also see the possibility of improving the charging schedule further. For that, I want to run a heuristic based on incumbent solutions that satisfy all constraints, including the continuity constraints. I hope my explanation is clear.
Do you think this is a reasonable approach?
0 -
Hi Buddi,
I hope my explanation is clear.
Yes, thank you for the explanation.
This is a quite complex situation. You are saying that solving your model without the complicating continuity constraints (I'll just call them ccc) seems "easy", but when you add ccc then finding feasible points seems to be a challenge.
I think there are multiple things you could try.
You could add all ccc to the model as normal constraints and try to tune some parameters to make Gurobi focus more on finding feasible points, e.g., MIPFocus, NoRelHeurTime, Heuristics. This way, Gurobi would take advantage of ccc in its presolving step and the final solution would directly satisfy all ccc.This would be the easiest approach if you can get this to work in acceptable time.
You could add a MIPSOL callback where you first get the incumbent via the cbGetSolution method. Then, you would add the particular ccc as lazy constraints that are violated by this solution to cut it off. You could still use the now infeasible solution to construct a new and hopefully feasible solution which you can then provide to Gurobi via cbSetSolution within the same callback call.
If the callback approach does not work for whatever reason, you could try to do it without callbacks. You could first solve a model without any ccc. After a successful optimization, you could take the feasible solution point, add all ccc which it violates as normal constraints to the model and provide this solution point as a MIPStart and re-optimize. This way, Gurobi can utilize the ccc in its presolve routines.
I would try the above approaches in the order as they are provided.
Best regards,
Jaromił0 -
This is a quite complex situation. You are saying that solving your model without the complicating continuity constraints (I'll just call them ccc) seems "easy", but when you add ccc then finding feasible points seems to be a challenge.
I find some feasible points, but the solution is hard to improve. I can heuristically find better charging schedules to improve the solution, which is what I want to do.
Anyway, I will try your suggestions and see if I can get better results. Thank you.
0
Please sign in to leave a comment.
Comments
4 comments