Redesing of BiDirectional

[torressa]

Given there's a fair few extensions to make, I think it's worth changing the structure a bit so that working on them is a bit easier.

Improvements/Features/Bugs include:

• Dominance and label elimination (discussed in #37)
• Parallelisation (also discussed in #37)
• min_res bug (raised in #41)
• Time limit parameter (discussed in #42)

The current structure doesn't lend itself that well to all of the above, therefore, I propose to split the current BiDirectional object into two. A Search helper object (for both backward and forward searches) and a modified BiDirectional object which will just orchestrate the searches and output the results.

Helper Search object

Purposes:

• Advancing the search
• Dominance checking
• Label elimination
  • [x] Elementary and non-elementary cases #37 #52
  • [x] Label feasibility #41

Individual Attributes (not shared)

• direction - direction of search
• unprocessed_labels nested dict with labels to help with label elimination.

Modified BiDirectional object

Purposes:

• Orchestrating the search
  • [x] In the original way (.run method)
  • [ ] In parallel (.run_parallel method) #37
  • [x] Stopping the search (time limit) #42
• Joining final labels
  • [x] Label feasibility #41
  • [x] Stopping early (path cost under an input threshold) #37

Individual Attributes:

• Resource bounds (shared for parallel search)
• best labels
• final label (to output the results)

[torressa]

Initial commit in branch patch43. Structure mostly set, just need to fix the interactions with the helper object.

[torressa]

Things ticked above are nearly done but need further testing:

• time limit
• threshold
• label elimination

[torressa]

Also, there should probably be a base object since there are a number of attributes that are shared between the the helper object and BiDirectional

[torressa]

Latest commit fixes unit tests! Parallel needs more testing

[torressa]

Elementary version doesn't work for the vrpy solomon instances.

[torressa]

Merge into dev as unittests passing, still needs work.

[torressa]

Works now on the solomon instances, like 10x slower than the old release...

[torressa]

https://github.com/Kuifje02/vrpy/issues/9#issuecomment-654394619

[torressa]

New work in branch patch43-v0.1.1. Reverted back to the latest release due to the slowness of the structure outline in the description of this issue. Will carry on with further speed up techniques to the future C++ version. There are some label pruning techniques that are really easy to implement and will provide an improvement (happens in python too if the problem is big enough); for instance see Lozano et al (2015) and Feillet et al (2004).

Will have to think about applying pruning techniques outside the algorithm, therefore allowing for other labelling algorithms to be easily implemented.

Time limit :heavy_check_mark: Threshold :heavy_check_mark: Dominance frequency :heavy_check_mark: Parallel :x: (deferred) Label elimination :x: (deferred)

[torressa]

Time limit going over quite significantly for large problems. Will release after fixing

[torressa]

Just committed work on the cpp branch

Remains to be done:

• [x] python packaging.

in tools/dev/ running ./build -p -r should create the python package and run the unit tests, however the dlls in .libs are not found by the python package.

• [x] ci Update 15/11: Set up using workflows for ubuntu (needs beautifying but works)
• [ ] benchmarks with direction = both
• [ ] add more benchmarks
• [x] use efficient labels (best_labels) as well as unprocessed to the dominance checks

[torressa]

Callbacks now working! Fails for bidirectional by I think it's a merging labels issue as it works for direction="forward". See example 8ac45b7fc4b69a11a4097f6e530a0042122bcd31 Broken python unittests: issue20, issue22, issue38 and issue41

[torressa]

Python unittests working on ubuntu! Once benchmarks are working we'll be good to go

[torressa]

Finally got it working on the solomon instances! @Kuifje02