Closed torressa closed 4 years ago
This is due to the label inversion being a bit trickier with custom REFs. I've implemented a really inefficient solution https://github.com/torressa/cspy/blob/master/cspy/algorithms/bidirectional.py#L561-L580
The proper way to do this would be to flip the initialisation of backward labels, such that instead of decreasing from the upper bound, they increase from the lower bound. Except the monotone resource which is required to decrease. This removes the need for an inverted backward REF, which is quite convenient for everyone.
It turns out it's quite hard to come up with a generic way to merge forward and a backward labels when custom REFs are given. It's really hard to guarantee the correct resource consumption. It's pretty easy per problem, I just can't see a generic fix.
The best solution I've come up for this is to create another input for BiDirectional that takes a function that does this.
https://github.com/Kuifje02/vrpy/issues/10#issuecomment-619194443
The addition of a new argument REF_join
in BiDirectional
removes the issue.
Allowing the user to define an appropriate function for merging two
https://github.com/torressa/cspy/blob/6ad0650e5baa27882594a0e4fe6a0c5835fb0504/cspy/algorithms/bidirectional.py#L82
Only required when custom REFs are used, and the joining of backward and forward paths requires some specific operations. For example, node-related resource extensions.
For an example for the case of the vehicle routing with time windows
https://github.com/Kuifje02/vrpy/blob/dev/vrpy/subproblem_cspy.py#L246
Docs need updating before next release
Describe the bug When running the BiDirectional algorithm in both directions and using custom REFs, the resulting
consumed_resources
attribute is wrong.