how to decrease the running time for a sequence optimisation
Awaiting user inputHello,
I got an optimisation problem that requires finding out the min/max value of the system at each time step (hourly) for 24 hours. The process is like, e.g., when the problem has to be optimised at t1, then the relevant variables at all other timesteps will be fixed by predefined value. So i used a loop in my model:
while k<24:
m.optimise()
k+=1
Initially, the model works very slowly, and someone told me that is because my problem is a MIP problem and the gurobi used the heuristic algorithm to address it, and when it comes to next step, the old heuristic solutions will be used by the solver, therefore leading to increased solve time.
then i updated the model to:
while k<24:
m.optimise()
m.reset()
k+=1
trying to Discarded solution information.
However I find the computational time of sequence optimisation is still much longer than I just optimise the problem time by time manually. E.g., in sequence optimisation, the model runs 2000s at t=11 to get the results but only cost me less than 1 min to do the same thing when I optimise it just at the timestep t=11.
-
-
Gurobi Staff
Hi Cass,
Initially, the model works very slowly, and someone told me that is because my problem is a MIP problem and the gurobi used the heuristic algorithm to address it, and when it comes to next step, the old heuristic solutions will be used by the solver, therefore leading to increased solve time.
It is often very hard to find feasible solutions for MIPs. Thus, Gurobi uses multiple heuristics in order to find and improve feasible solutions during the solution process. In your first loop, Gurobi will re-use the optimal solution found in the previous optimization run as a MIP start for the subsequent one, see How do I use MIP starts?
Using a MIP start often improves solution performance, because the solver has to spend less time searching for a first feasible solution and can use an already given one and try to improve it. However, it is not guaranteed that this works out well. Gurobi uses solution information to guide specific heuristic into several directions of the solution space, but if the originally provided solution is not very good in terms of quality and/or objective value, it may actually lead to a performance degradation as the solver spends time trying to improve a bad solution, ultimately leading far away from the actual optimal solution of the given model.
Unfortunately, it is usually not possible to say a priori whether a MIP start would be beneficial for a problem or not. In your case it looks like it is not beneficial to make use of previously found solutions, thus using the second loop should be better.
In general, you might want to have a look at Most important parameters for MIPs in order to improve the overall performance of your sequential optimization. If you are aware of any particular difficult instances, e.g., t=11, then it might make sense to try to find parameters which improve the performance of these instances and apply those to all instances in the algorithm to boost the overall performance. You might also want to have a look at Gurobi's automatic tuning tool.
Best regards,
Jaromił0 -
-
Hello Jaromił
Thanks for the reply. I know a MIP problem can be sometimes tough to be solved. But here the trouble that I met is not mainly caused by MIP.
The loop I added in my model just aims to help me automatically update the time step, it should not increase the computational burden for each one, neither do enlarge the size of the problem itself. For example, if i just implement my case for every time step manually, it just cost me around several mins per optimisation. But once after I added a loop to avoid reading the EXCEL input file each time step, for saving time, but then for each optimisation that should be solved within minutes, becoming time consuming.
So im wondering the reason behind that, e.g., memory issues? algorithm issues? ...etc. As well as how to solve this.
Many thanks!
Cass
0 -
-
-
Hi Cass,
To investigate this issue, you should have a look at the models being solved when you solve the models 1 by 1 and when you solve these models in sequence.
You can use the write method to write a human-readable LP file which you can analyze in any standard text editor. If there is no difference between all models solved 1 by 1 and the models solved in sequence then, we can investigate further.
Best regards,
Jaromił0 -
Please sign in to leave a comment.
Comments
3 comments