Skip to content

Use Eval struct over plain Cost/Gain types#752

Merged
jcoupey merged 18 commits intomasterfrom
refactor/eval-and-gain-as-struct
Sep 6, 2022
Merged

Use Eval struct over plain Cost/Gain types#752
jcoupey merged 18 commits intomasterfrom
refactor/eval-and-gain-as-struct

Conversation

@jcoupey
Copy link
Copy Markdown
Collaborator

@jcoupey jcoupey commented Aug 1, 2022

Issue

Fixes #738

Tasks

  • Create data structure to replace Cost and Gain values
  • Adjust helper functions
  • Adjust heuristics client code
  • Adjust operators client code
  • Adjust local search code
  • Benchmark timing impact
  • Update CHANGELOG.md
  • review

@jcoupey jcoupey added this to the v1.13.0 milestone Aug 1, 2022
@jcoupey
Copy link
Copy Markdown
Collaborator Author

jcoupey commented Aug 2, 2022

I've run this PR against the usual benchmarks across various exploration levels.

Solution obtained

All solutions are strictly identical with current master and this PR so it looks like I did not break anything with all the adjustments to switch from Cost/Gain to the new Eval struct.

Timing

Computing time increase is in the +15 to 20% ballpark for CVRP and VRPTW instances and around +5 to +10% for PDPTW instances. So this will somehow eat a bit of the performance boost that was introduced in the latest release, but there is not really any other way around that I'm afraid.

Possible improvement

The new Eval struct holds both cost and duration metrics and all the math operations are overloaded to operate on both members. So the computing overhead is due to switching from doing cost/gain math with basic types (uint32_t and int64_t) and a single value to doing it with this struct. I've implemented the various operators in a straightforward way but maybe it's possible to do a bit of compile-time magic to improve the efficiency here. Any input on that is welcome!

@jcoupey jcoupey merged commit 7df874c into master Sep 6, 2022
@jcoupey jcoupey deleted the refactor/eval-and-gain-as-struct branch September 6, 2022 13:30
@jcoupey jcoupey mentioned this pull request Sep 7, 2022
24 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Store several metrics in costs / gains

1 participant