Speed ups: BiDirectional

[torressa]

For some real cases, the BiDirectional algorithm is slow and sometimes stalls.

Here are some thing that can be done to speed things up.

Dominance checks

• [ ] Rework best_labels so that dominance rules don't have to be applied twice.
• [x] Experiment with running full dominance checks at different frequencies
• [x] Apply the discarding property (non-elementary version was used in and every version prior to v0.0.12)

Frequency

How often dominated labels are checked affects the algorithm, checking it after every iteration is probably not the best idea.

Discarding

In the non-elementary case, the dominated label and all of its extensions can be discarded, providing a significant speed up. In the elementary case a similar rule can be applied. See Irnich and Desaulniers (2005) page 15.

Stopping Early

If a threshold cost is given, the joining procedure can be stopped early if the resulting path has a total cost under the threshold. In the column generation setting, the threshold would be 0.

C++

A possibility is to translate the algorithm into C++ and call it from python.

• [x] Do some research about interfacing C++ and python (should be alright)

Parallel

I have a terrible implementation in parallel using ray that works for some toy cases. However, as soon as you start passing custom REFs everything starts exploding. Even though I don't like the extra dependency it's pretty convenient as there are some shared arrays between the forward and backward processes.

• [x] Commit to new speedups branch.

Profiling

Some profiling with line_profiler (cspy.BiDirectional) :

~77% of the time is consumed by self._algorithm(direct)

~50% consumed by deque(map(self._propagate_label, edges, repeat(direc, len(edges)))) ~20% consumed by self._check_dominance(next_label, direc)

• [x] Try for loop instead of deque(map())

Originally posted by @Kuifje02 in https://github.com/Kuifje02/vrpy/issues/9#issuecomment-612439674

[torressa]

I think it might be possible to parallelise the searches using ray. It's a pretty big dependency though

[Kuifje02]

wow ! that is a brilliant idea. Would be very nice indeed !

[torressa]

Tried for-loop instead of deque(map()) and is faster in most cases.