Static move descriptors (SMDs) about euro-neurips-2022 HOT 3 CLOSED

A priori the purpose seems similar to the nbMoves/last tested/last modified caching mechanisms that are in LocalSearch already. I need to think a bit about whether this is more powerful than what we already have. I think yes, but I want to get an estimate for how much more this will save before implementing it.

from euro-neurips-2022.

That was quick. The answer is definitely yes: we currently only look whether U's or V's route have been modified more recently than the last time U was evaluated. But routes can be modified in places that have nothing to do with the few nodes we're considering moving. SMDs take this into account, and should thus be much more efficient at caching delta costs than what we currently have.

from euro-neurips-2022.

I've attempted to implement something like this, but it doesn't really work well with the current operators. Instead, I've improved caching for particularly SWAP* in #64. That helps quite a bit as well.

I think we can close this issue.

from euro-neurips-2022.