Bidirectional not finding valid path when using negative resource consumption

[steveharenberg]

Describe the bug The bidirectional algorithm is not finding valid path with negative resource consumption.

To Reproduce

from cspy import BiDirectional

max_res = [6, 100]
min_res = [0, -100]

def createG():
    H = DiGraph(directed=True, n_res=2)
    H.add_nodes_from(['Source', 1, 2, 3, 4, 'Sink'])
    H.add_edge(2, 3, res_cost=[1,1], weight=1)
    H.add_edge(3, 4, res_cost=[1,1], weight=1)
    H.add_edge(4, 'Sink', res_cost=[1,1], weight=1)

    return H

# This works
H = createG()
H.add_edge('Source', 1, res_cost=[1,1], weight=1)
H.add_edge(1, 2, res_cost=[1,-1], weight=1) # -1 cost here
bidirec = BiDirectional(H, max_res, min_res, elementary=True, direction="forward")
bidirec.run()
print(bidirec.path)

# This finds no path
H = createG()
H.add_edge('Source', 1, res_cost=[1,-1], weight=1) # -1 cost here
H.add_edge(1, 2, res_cost=[1,1], weight=1)
bidirec = BiDirectional(H, max_res, min_res, elementary=True, direction="forward")
bidirec.run()
print(bidirec.path)

Expected behavior There is one valid path from source to sink which is not found when putting a negative resource consumption at the first traversed edge. I think that this issue generally arises when the cumulative resource dips into negative values regardless of whether that is valid bad on the min_res.

Desktop (please complete the following information):

• OS: Linux
• Version 1.0.1 (vrpy_patch15 does not work either)

Suggestions TBD

[torressa]

Thanks for another one! This is kind-off related to previous one. I transform the minimum to resources to a vector of 0s if one is not given. https://github.com/torressa/cspy/blob/452aaeaca6a63e5ed21b7c0059f6c4b437dbdce4/src/cc/bidirectional.cc#L131-L143

In the second case, the resource at index 1 will already be infeasible wrt the artificial min_res_curr_ in the code through the only source edge (as -1 < 0), although clearly feasible wrt to the original min_res. If the direction="both" it works as I presume the path is found backwards.

I added this as otherwise when checking partial paths wrt a positive minimum resource bounds (like the one in #89) the algorithm would not be able to advance. Also makes the arithmetic easier when transforming backward labels into forward ones for merging.

I'll have a think and see what the best approach is here.

Options:

1. (In the case of min_res not all 0.0) Bypass checking the minimum resource bound when extending labels, and only check when saving them?

[torressa]

@stevenharenberg Update:

https://github.com/torressa/cspy/blob/452aaeaca6a63e5ed21b7c0059f6c4b437dbdce4/src/cc/bidirectional.cc#L131-L143

Removed this fudge on the patch90 branch. Now min_res_curr_ is just min_res except that during the algorithm the index of the critical resource (params_ptr_->critical_resource) contains the halfway point (same as before). However, the first labels are initialised to a vector of 0.0s (except for the critical resource for the backward label).

Options:

1. (In the case of `min_res` not all 0.0) Bypass checking the minimum resource bound when extending labels, and only check when saving them?

Using a version of this. Introduced "soft" feasibility checks (in Label.checkFeasibility) which now has a special behavior when checking lower bounds. If "soft" check, then the lower bound is only checked if either for the critical resource index or if min_res[i]<= 0. If not "soft", then all lower bounds are checked as expected.

Currently non-elementary forward for test #89 on H is failing (need to investigate why this is...). FAIL: test_forward (tests_issue89.TestsIssue89) (see here) Tests for this issue seem to work fine (tests/python/tests_issue90.py).