More acceptance criteria

[N-Wouda]

Santini et al. (2018) present a lot of them in their paper. I implemented three that seemed promising, but to be thorough we should probably also get the rest in.

[N-Wouda]

Should also check that implementations of current algorithms agree with the reference. For SA/HC I am pretty sure they do, for RRT not entirely.

[leonlan]

I can help with implementing more acceptance criteria. Will submit a pull request when I have a few ready. I'll work through the criteria presented in Santini et al. (2018) and work from top to bottom.

[N-Wouda]

@leonlan sure! A lot of them seem superficially similar, so it might be possible to reuse a lot of code for (slightly) different acceptance criteria.

[leonlan]

Should also check that implementations of current algorithms agree with the reference. For SA/HC I am pretty sure they do, for RRT not entirely.

The description of RTRT in Santini et al. (2018) is different from the one you implemented, which follows the original paper by Dueck and Scheuer (1990).

# Santini et al. (2018)
result = (candidate.objective() - best.objective()) / best.objective() <= self._threshold

# Dueck and Scheuer (1990) 
result = (candidate.objective() - best.objective()) <= self._threshold 

What is your thoughts on this? Change to Santini's description or keep the original? I might prefer the latter, because it makes semantically more sense to have a threshold on the absolute gap instead of the relative gap.

[N-Wouda]

What is your thoughts on this? Change to Santini's description or keep the original? I might prefer the latter, because it makes semantically more sense to have a threshold on the absolute gap instead of the relative gap.

I am inclined to keep things as they are. We might add an argument to RRT's init method to select behaviours (e.g., "original" for Dueck and Scheuer, and "santini" for Santini's implementation with the normalised thresholds - with the default being "original"). Then we get the best of both worlds!

Odd that Santini implemented such a different version, but they probably had their reasons :-).

(good job with the release of v1 of https://github.com/leonlan/pyCVRPLIB! Congrats!)

[leonlan]

I am inclined to keep things as they are. We might add an argument to RRT's init method to select behaviours (e.g., "original" for Dueck and Scheuer, and "santini" for Santini's implementation with the normalised thresholds - with the default being "original"). Then we get the best of both worlds!

Odd that Santini implemented such a different version, but they probably had their reasons :-).

OK, will put it on the to-do.

(good job with the release of v1 of https://github.com/leonlan/pyCVRPLIB! Congrats!)

Thanks! I learned a lot from contributing to the ALNS library (e.g., poetry, gh-actions), so thank you for that :)

[N-Wouda]

I'm closing this issue because the last series of PRs (#77, #78, #79, #80, #81, and #82) have significantly extended the number of acceptance criteria on offer. These will be released in v4.1.0, after PR #87 is merged in.