Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Timeout option has no effect #792

Closed
kkarbowiak opened this issue Sep 28, 2022 · 9 comments · Fixed by #807
Closed

Timeout option has no effect #792

kkarbowiak opened this issue Sep 28, 2022 · 9 comments · Fixed by #807
Labels
Milestone

Comments

@kkarbowiak
Copy link
Contributor

It seems that timeout option (the third parameter to vroom::Input::solve function or --limit command-line parameter to the stand-alone binary) has no effect.

I have a problem that takes about 45 minutes to solve using vroom. I tried to use the timeout option to see how much the results will differ if I want to have the results earlier. I tried passing the timeout (1000 and then 600 seconds), but even with it I still had to wait 45 minutes for the results.

I tried binary built using:

  • latest master (b0fcb1b)
  • v1.12.0 release
  • v1.11.0 release (when the option was introduced)

I tried the three binaries on Manjaro.

Can someone please confirm (@jcoupey maybe)? I can give some more details if needed and am willing to try and investigate more.

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 28, 2022

There is a subtlety in the way timeouts can behave, especially for big instances. If the one you're looking at requires 45 minutes of solving, my guess is this is what you are hitting. Basically the timeout idea is to "exit with the best current solution after X seconds", but it does not really make sense to exit when we don't even have a "full" solution from the heuristic process. So in practice we throw the usual initial solution building using heuristics not matter what, then during local search we periodically check for timeout. The heuristic computing times are negligible compared to the local search times so in most situations we do get a full solution under the limit and the timeout works as expected. The problem arises if the heuristic process takes longer than the timeout you input. Think of it another way: for a very hard problem that is especially big, you can't expect to put arbitrary low computing times and get a solution at all (let alone a decent one).

In practice, this means that when using -l 0 you won't get an instant solution, but a way to measure how long it takes to run the heuristic process alone, without local search. What is the computing time on your instance when using -l 0?

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 28, 2022

FWIW, the idea in #509 could also reduce the heuristic computing times by an order of magnitude, especially for big instances.

@kkarbowiak
Copy link
Contributor Author

Thanks for the comments.

I think I mostly understand how the timeout works and I do realise the timeout does not affect heuristics (it was clearly stated in #594 (comment)).

I will check the computing time with -l 0 and will try to measure the heuristics phase.

@kkarbowiak
Copy link
Contributor Author

Alright, I repeated the computation

  • with no -l it took 39 min 21 sec (vroom reports 4'107 loading and 2'357'703 solving times)
  • with -l 0 it took 36 min 10 sec (4'161 loading and 2'166'669 solving)

and the optimisation results do differ.

So it seems that indeed it was the heuristics phase that consumed this much time.

@jcoupey Do you have any insights on under which conditions the heuristic phase can take this much time (as opposed to being near negligible with regards to time used by local search)? Do you think it might be beneficial to have separate entry for heuristics in computing times in summary?

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 28, 2022

Do you have any insights on under which conditions the heuristic phase can take this much time

I'd say mostly problem size (that is number of jobs and number of steps for the computed routes), but having specific constraints may also enter into play.

Can you by any chance share the instance you're using, either here or privately?

@kkarbowiak
Copy link
Contributor Author

Sorry for slow response. I think I will be able to share something.

Meanwhile, I had a look at cvrp.cpp and vrptw.cpp. In both, the solve function splits work to available threads and each of the threads runs a loop. Each loop iteration runs a heuristic and then local search.

I added some log messages and confirmed that the local search steps for lower ranks do execute before heuristics for higher ranks. The timeout would work better if all the heuristics were allowed to finish before starting local search. I will prepare a modification and see how it fares. In my opinion it should work, but perhaps there are some other considerations I did not think of.

@jcoupey jcoupey added bug and removed question labels Oct 4, 2022
@jcoupey
Copy link
Collaborator

jcoupey commented Oct 4, 2022

Ah right I get it now: all local searches are stopped as expected, but all the heuristic processes scheduled for a single thread are done no matter what.

The timeout would work better if all the heuristics were allowed to finish before starting local search.

I guess that would be the best way to fix this timeout problem. Actually I nearly did that recently in #750, see comments in the ticket and associated PR for why I finally reverted some of the changes.

@jcoupey jcoupey added this to the v1.13.0 milestone Oct 21, 2022
@jcoupey
Copy link
Collaborator

jcoupey commented Oct 21, 2022

@kkarbowiak can you confirm that #807 does fix the problem? Also happy to get any feedback on the changes over there.

@kkarbowiak
Copy link
Contributor Author

@kkarbowiak can you confirm that #807 does fix the problem? Also happy to get any feedback on the changes over there.

Yes, it does. With #807 all the heuristics complete strictly before the local search phase. Having in mind that the timeout does not affect the heuristics phase, it works as advertised.

I also observed a ~10% improvement in solving time, but this is based on limited testing and may not be representative.

Let me also comment on the PR.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants