Preprocessing fails to find nodes and may find incorrect nodes about cspy HOT 5 CLOSED

Sounds good, thanks for taking a look and merging. Great library by the way! Happy to help make it even better.

from cspy.

Hey again @dvbuntu, thanks for bringing up another bug!

There are some preprocessing techniques but most of them use the source-to-all shortest paths which has to run twice (one for each direction) and then times the number of resources. So it can get really slow.
Also, they are only effective on certain types of networks (e.g. doesn't work on connected graphs like the ones you get in VRP instances).

In a recent paper, link found in #67, has a much faster and elegant solution to this. They also have a crazy good implementation
Haven't gotten round to implementing it yet, but was definitely one of my priorities.

You are very welcome to open a PR with the fix for this :) the workflows will show if the test pass.
The build process is pretty straight forward if you set up docker, or alternatively install cmake on your machine.

from cspy.

Looking at the preprocessing more closely, I'm not sure that it's checking the min_res correctly. It looks for minimum weight paths and checks if the shortest path (for a given resource) is less than the minimum constraint. But if the shortest path is too short, there could be some longer path which is valid.

Ideally, we'd check if the longest path is not long enough. But we can't just make the weights negative and look for the shortest since that will likely introduce negative-weight cycles (for the original weights being positive). But the Longest Path Problem is NP-Hard, so we're not going to have a quick way to do this check. We may want to just avoid checking the minimum constraint in the preprocessor.

from cspy.

PR #74 opened to address this and some closely related bugs.

from cspy.

Thanks for the PR and for taking some time to think about this, it is greatly appreciated!
Everything passed so just merged it, the release wheel won't work as it needs another version number but will sort it out with the other stuff (#68, #69, etc).
I'll leave this open until then

from cspy.