Enforce ClpSimplex to start from status/solution of previous run

[constantinosTsirogiannis]

Hi all,

First of all, thanks again for all the effort that you are putting in the development and maintenance of this project.

I have the following problem: I am executing successive runs with the same ClpSimplex object, and sometimes between two runs I need to change the weights of my objectives, together with the bounds of some existing constraints. Whenever this happens, I notice that the runtime of the new execution goes up disproportionately. When checking the log of the execution, I see that the algorithm starts from an objective value which is far from the value of the solution where I ended up in the previous run. In fact, the solution of the previous run is usually very close to the optimum of the new run. Nevertheless, the algorithm starts from a very bad objective value and takes lots of time to converge. Also, ClpSimplex always chooses to solve the dual problem in these cases, as opposed to solving the primal problem on all other runs. My code is calling the dual() function, but apparently the simplex implementation may choose by itself either of the dual or primal problems to solve.

I understand that changing the objective weights can lead to a much different problem instance, and it would make sense that things are slow if my former solution is very bad compared to the new optimum. However, I have the impression that in the described setting, ClpSimplex dumps any previous status and starts to solve the entire problem from scratch. Therefore, is there any way to enforce ClpSimplex to start solving from the same status where it ended in the previous run, as it happens when I do not update my objectives? If yes, should I postpone adding any additional constraints to my problem before I start the run with the updated objectives?

Thanks in advance for the help,

--Costas

[jjhforrest]

Try forcing primal so - ClpSimplex  model; // first time model.dual();  while (not finished) {   // add/delete rows and modify objective   model.primal(1);  } Or maybe // add rows model.dual(); // modify objective mode.primal(); If second way looks reasonable you could save a small amount of time by looking at other parameters to primal to save factorization I can look further if you send information/data

…

On 31/01/2022 11:05, constantinosTsirogiannis wrote: Hi all, First of all, thanks again for all the effort that you are putting in the development and maintenance of this project. I have the following problem: I am executing successive runs with the same ClpSimplex object, and sometimes between two runs I need to change the weights of my objectives, together with the bounds of some existing constraints. Whenever this happens, I notice that the runtime of the new execution goes up disproportionately. When checking the log of the execution, I see that the algorithm starts from an objective value which is far from the value of the solution where I ended up in the previous run. In fact, the solution of the previous run is usually very close to the optimum of the new run. Nevertheless, the algorithm starts from a very bad objective value and takes lots of time to converge. Also, ClpSimplex always chooses to solve the dual problem in these cases, as opposed to solving the primal problem on all other runs. My code is calling the dual() function, but apparently the simplex implementation may choose by itself either of the dual or primal problems to solve. I understand that changing the objective weights can lead to a much different problem instance, and it would make sense that things are slow if my former solution is very bad compared to the new optimum. However, I have the impression that in the described setting, ClpSimplex dumps any previous status and starts to solve the entire problem from scratch. Therefore, is there any way to enforce ClpSimplex to start solving from the same status where it ended in the previous run, as it happens when I do not update my objectives? If yes, should I postpone adding any additional constraints to my problem before I start the run with the updated objectives? Thanks in advance for the help, --Costas — Reply to this email directly, view it on GitHub <#227>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHA23PMNDH57PBPWQGLUYZUINANCNFSM5NF5ZP3Q>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[constantinosTsirogiannis]

Thanks a lot for the quick reply! I will try both of these suggestions and see which works better.

--Costas

[constantinosTsirogiannis]

Just a clarification: in the first suggested alternative, is it:

model.primal(1) ;

or

model.primal(0,1);

?

[jjhforrest]

model.primal(1); This does a "values" pass (and you should get a message when it ends).  If you added/modified constraints then the basis may be singular so variables are thrown out of basis.  With 0 they would go to one of their bounds; with 1 they are left at their current value and marked as superbasic. Then a pass is done through model moving those variables up or down as the code thinks best - this is based on feasible and infeasible reduced costs and so can be influenced by the choice of infeasibility cost - the default starting value is fairly high and can be changed by setInfeasibilityCost - but try default first. If you just deleted constraints then the starting solution will be feasible. The second parameter is for really fine tuning of algorithms.

…

On 01/02/2022 20:17, constantinosTsirogiannis wrote: Just a clarification: in the first suggested alternative, is it: model.primal(1) ; or model.primal(0,1); ? — Reply to this email directly, view it on GitHub <#227 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHGJAQ6XTECT3FJWT7TUZA5XJANCNFSM5NF5ZP3Q>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you commented.Message ID: ***@***.***>

[constantinosTsirogiannis]

I tried both, but unfortunately I did not gain any runtime improvement.

When using the value pass option, every call to simplex would switch to dual in the middle of the execution, resulting in 2-3x runtime degradation.

I also did not observe any runtime improvements when using the option where first dual() is executed after a major objective change, and then follows an execution where the primal is used if I need to add any new constraints. I attach here a summary with the series of executions for each option used, indicating where there has been any objective changes. Let me know if you see any potential in improving the runtime with other options.

with_value_pass.txt

dual_for_objective_change_and_primal_for_added_constraints.txt

[jjhforrest]

I presume the with.. run was on a slightly faster computer than dual.. based on first few lines of output.  I also presume that in Current size: 2338782 Constraints: 317041 the current size is number of non-zero elements - not number of variables. Possibilities to make faster - a) build a faster version of Clp - e.g. use openblas. b) profile a run and see where it is spending time.  It is probable that it is refactorizing too frequently.  There may be other simple changes. c) it looks as if major changes to objective are when long runs happen - maybe solve those from all slack - if number of iterations does not go up much then will be faster due to sparser factorization. d) if you can put up a version of long running problem and previous optimal basis (without interesting column/row names), then I can take a look.

…

On 11/02/2022 12:42, constantinosTsirogiannis wrote: I tried both, but unfortunately I did not gain any runtime improvement. When using the value pass option, every call to simplex would switch to dual in the middle of the execution, resulting in 2-3x runtime degradation. I also did not observe any runtime improvements when using the option where first dual() is executed after a major objective change, and then follows an execution where the primal is used if I need to add any new constraints. I attach here a summary with the series of executions for each option used, indicating where there has been any objective changes. Let me know if you see any potential in improving the runtime with other options. with_value_pass.txt <https://github.com/coin-or/Clp/files/8048640/with_value_pass.txt> dual_for_objective_change_and_primal_for_added_constraints.txt <https://github.com/coin-or/Clp/files/8048642/dual_for_objective_change_and_primal_for_added_constraints.txt> — Reply to this email directly, view it on GitHub <#227 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHHXLFJZQ325XJWSAGDU2T74RANCNFSM5NF5ZP3Q>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you commented.Message ID: ***@***.***>

[constantinosTsirogiannis]

Thanks again for the answer.

I will definitely try (a), about (b) I think the logs usually show at most one re-factorization per run, so I am not sure if this affects the runtime too much.

Also (c) sounds very interesting, could you provide more details on how to do that?

[jjhforrest]

On 11/02/2022 20:31, constantinosTsirogiannis wrote: Thanks again for the answer. I will definitely try (a), about (b) I think the logs usually show at most one re-factorization per run, so I am not sure if this affects the runtime too much.

On b) - the output for part of run is - Clp0006I 0  Obj -14499126 Primal inf 0.55432744 (14) Dual inf 1.1105353e+09 (15963) Clp0006I 0  Obj -14499126 Primal inf 0.55432744 (14) Dual inf 1.4939455e+15 (17799) Clp0006I 200  Obj -14497928 Dual inf 2.66535e+09 (16282) Clp0006I 400  Obj -14495117 Dual inf 2.5223655e+09 (16276) The code was using primal algorithm (so minimizes objective + X * sum of primal infeasibilities) - factorized the basis and decided to increase X.  By iteration 200 the code was primal feasible so just reports on dual infeasibility.  Each line of output 200,400.. is when it refactorizes the basis. Try saving initial problem and play around with standalone clp on that problem.  You will probably see that it does more than 200 iterations between refactorizations.  You may also see a message about perturbing problem.  If you do try turning perturbation off.  If that is slower then perturbing problem helps and as you are doing multiple runs there is more that could be done.

Also (c) sounds very interesting, could you provide more details on how to do that?

model.allSlackBasis();  try default of false to start.

…

— Reply to this email directly, view it on GitHub <#227 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABWJYHETQJC5FUSDCBXSBO3U2VW37ANCNFSM5NF5ZP3Q>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you commented.Message ID: ***@***.***>

[constantinosTsirogiannis]

Sorry for the extremely belated reply. And once again, really thanks for the feedback and help. I just wanted to close this by saying that I tried to fiddle with the perturbation options but nothing worked better than the actual default.

Thanks again!