Multi-seed MIP Start for hierarchichal receeding horizon optimization
Dear Gurobi team,
I am currently dealing with a Lexicographic MPC, implemented using gurobipy API. I believe it would be a great feature with potentially great perfomance benefits the possibility to add multiple MIP start, multiple candidate starting solutions, for MILP problems like mine. I believe so because, as you go down the priority objective chain, let's say from L1 to L2, the solution that L2 starts with is that of the “optimal” L1, however, that L1 “optimum” completely ignores the objective of L2, which is completely logic. Nonnetheless, in receding horizon schemes such as Model Predictive Control, a great warm-start strategy is to use the shifted solution from the previous call (which it would also be great to be able to just check an option called “shift previous” in gurobipy), which is somewhat contradictory with your hierarchichal optimization approach. Even if I take the shifted solution from the lowest priority objective from time instant k-1 and use it as the starting solution for L1 at time instant k, the solver might find a previously pruned/unrefined solution that is specifically focused on only optimizing L1 which makes the whole optimization burden from instant k-1 useless in the perspectives of L2 downwards, at L2 the solver will, in many instances, have to search again for incumbents or improve the bound because the solution passed down from L1 at instance k completely ignores what was done at L2 in time instant k-1.
I believe a hybrid approach would be best, somehow a MIP start approach that could take multiple incumbents at once and start from the best. Imagine for my problem, at time instant k I could pass warm-start L1 with the shifted solution from the k-1 lowest priority objective, then at L2 the solver gets BOTH the upstream L1 re-optimized objective but also (as an external input to the hierarchical chain) the SAME shifted solution from instant k-1 that L1 received. I believe that in maaaaaany instances, the shifted solution will be a better candiate for multiple levels than the upstream solution per-se which would translate to computational load decrease. I know I could build this “custom” hierarchical optimization procedure by hand, but your proprietary warm-starting approach is faster and more reliable.
Sorry if my English is not perfect.
-
-
Gurobi Staff
Dear Pol,
At the end of your post, you wrote:
your proprietary warm-starting approach is faster and more reliable
I don't think there is anything specific in the way Gurobi solves multiobjective problems that makes our warm-starting of each step "faster and more reliable". If you would implement the multiobjective loop yourself, I don't think you would lose anything in terms of warm-starts. And, as you noticed, you would gain the ability to specify multiple MIP starts for each round.
This being said, let me try to restate your suggestion, to make sure I understood it correctly…
You would like that the MIP start given at the beginning of the multi-objective solve is used as a MIP start for _each_ of the optimization rounds of the multi-objective solve at instant k, in addition to the solution from the previous optimization round.
Did I get that right?
I probably missed something, because I don't see how this would help. If the MIP start is optimal for the first objective, this will be the solution at the end of that optimization round: Gurobi has no reason to look for another solution, and in any case will not find one that's better (in terms of L1) and would replace the MIP start as the incumbent. So the MIP start _will_ be the solution given to the lower priority objective as well.
If the MIP start is not optimal for L1, then it will not be feasible for L2, because a constraint will have been added to make sure that the optimization of L2 doesn't degrade the solution in terms of L1. And then it will have to be repaired before it is accepted as a MIP start for L2. That repair step would potentially be as expensive as solving for L1 to begin with, and Gurobi will probably stop way before that, and not accept the MIP start for the L2 step. It would therefore not help.
Did I miss something?
0 -
-
Dear Xavier,
About the reliability of custom hierarchical loops. I've had edge cases, not specifically with gurobipy, but with YALMIP or similar, in which getting back the solution from Gurobi at L1 and then passing it to Gurobi again with an L2 objective made the MIP start infeasible and, in other cases, even the L2 problem infeasible due to numeric noise. I had to devise “cone-like” approaches in which I truncate/approximate the inputs to the problem deeper, with more resolution easing feasibility, as you go down the priority chain. In MPC design and simulation, where you repetitively run the same problem with different inputs, these infeasibles really break the whole simulation, and I did not know how to be robust to them. Since moving to your proprietary hierarchical loop, I've never had lower-level objectives break feasibility, and I hope it does not happen again, so I strongly do not want to move away from your implementation.
- Did I get that right?
Yes, exactly.
- Did I miss something?
I think so. Let me put more context about my type of problem. I have multiple upper-level objectives which are “active-set objectives” , let's say cost increases +Y iff variable ≥ threshold, otherwise, cost 0. Thus, the optimal solution can be non-unique, which is my case. But I made/designed it this way to help lower-level objectives have optimization headroom based on the problem formulation itself, not on solver parameters. Moreover, in MPC settings, the solution time is constrained or, at the very least, should be considered for real-world application. For this reason, I devised a custom callback in which the solver is stopped after a certain time budget, but the time budget only starts to be consumed after finding the first incumbent (which could also be an interesting Gurobi feature), otherwise, you can get infeasibles just because the first incumbent was too hard and break the simulation. Basically, I limit the incumbent improvement or proof of it by a time budget on a per-level basis; this way I can somewhat benefit from the fact that the global chain time budget, imposed by the hard “timeLimit” of yours, is utilized to go through multiple priority objectives. Otherwise, in a constrained solution time setting such as MPC, you could get the whole time budget consumed by proving the L1 objective, for example, and never even touch L2 or L3.
I am aware this kind of problem formulation might not be the strongest, but sometimes you don't know better.
With this context, assume the optimal solution can be non-unique in some priority levels since the problem might have some combinatorial nature, and the time budget is constrained. The computational effort put into the previous solve instance, k-1, which has optimized L1 through L_last, could potentially be quite worthwhile to consider for time instant k. Thus, a multi-seed or “exogenous MIP Start” implemented in your hierarchical chain could have some computational benefit.
Another way of putting it, if you are at L2 and you have to search for solutions, you end up finding that there are multiple choices with the same cost, you might choose option A. However, if you kept the context of instance k-1, by the “exogenous warm start”, an almost full solution, option B, already existed and completing it is trivial and feasible; choosing that solution is even better, I think, because it was proven to also optimize lower-level objectives (L3, L4, etc). Thus, at L3, you won't even need the exogenous warm start, because the upstream completed option B might also be optimal for L3.
Am I explaining myself? Maybe I am also wrong.
0 -
-
Okey, I missed something.
If the k-1 solution is truly a valid incumbent at L1, you would only spend time closing the lower bound, but it would also be feasible through L2 downwards, which would make my feature useless. But aren't there instances in which, while improving the lower bound, the solver might change the incumbent solution for another one of the same cost, just due to some randomness in the heuristics or even at the presolve part? If that is the case, could my idea become interesting?
My final goal is that for repetitive solver calls, in the case of MPC, the past computational effort could be more valuable, and I think that the key is the previous solution, and Gurobi could greatly exploit “past knowledge on the problem” for repeatively solve the same problem, just with different inputs. Maybe there are some parts of the LP relaxation or the presolve or heuristics phase that, if the user of Gurobi parametrises “the problem is repetitive, only inputs change”, could benefit from some “previously solved instances" of the same problem. Maybe there could be an initial problem structure analysis and exploitation from Gurobi, that leaves a “more prepared” model for repetitive solve calls, like a “hot start” status. I am just dreaming now. It is just that in MPC you see time spent everywhere by the solver and start thinking that there should be a better way, knowing beforehand that it is not a “solve only once, not twice” problem.
0 -
-
-
If the k-1 solution is truly a valid incumbent at L1, you would only spend time closing the lower bound, but it would also be feasible through L2 downwards, which would make my feature useless.
I think you meant “if the k-1 solution is optimal for L1 […]”. And yes, that is correct.
But aren't there instances in which, while improving the lower bound, the solver might change the incumbent solution for another one of the same cost, just due to some randomness in the heuristics or even at the presolve part?
Gurobi would not do that. An incumbent is replaced only by a solution that strictly improves the objective value.
Presolve can remove some optimal solutions from the search space, when it knows that there are still some optimal solutions left. But doing so doesn't, by itself, change the incumbent. The incumbent will only be changed if another solution is found that has a srictly better objective value.
0 -
-
-
With respect to “solving not just once”, you may be interested in some research avenue we are pursuing, where one defines a ‘parametric’ model and uses both ML and Optim to provide very good solutions. This was presented in this webinar.
0 -
-
That solves my question.
Exciting to know about this research effort. I will watch the webinar.
Thanks again, Xavier.
0 -
Please sign in to leave a comment.
Comments
6 comments