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

Remove heuristic synchronisation #1188

Open
jcoupey opened this issue Nov 13, 2024 · 0 comments
Open

Remove heuristic synchronisation #1188

jcoupey opened this issue Nov 13, 2024 · 0 comments

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Nov 13, 2024

Back in #750 I introduced a mechanism to deduplicate solutions after the heuristic phase. The rationale was to avoid performing the exact same local search on identical solutions across different threads. While this is interesting in theory, there are drawbacks:

  • the code is much more complex with two multi-threading phases and a deduplication phase;
  • it requires a synchronization point across heuristic threads, which means "fast" heuristic searches are idle before all have completed.

This mechanism may reduce overall computations, but will in most situation not improve completion time, and could even harm it. Another consideration is that identical heuristic solutions happen quite a lot in small/simple benchmark instances (e.g. Solomon C class) due to the nature of the instances and the costs (rounded euclidean distances), but are pretty rare in a real-life setup with a significant number of locations and travel times to the second.

All this to say I think this is not worth the trouble and we should refactor that bit.

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

No branches or pull requests

1 participant