Dominance check for elementary paths about cspy HOT 10 CLOSED

Thanks for raising this! I always get confused.

I think the version in master is correct (apart from the equality check which is wrong). Just pushed a new unit test to the monotonic-resource-checks branch. Please check that it makes sense.

Your proposed version works fails on the new unit test, and also on the benchmarks (change the path in test/cc/test_benchmarks and then make benchmark). It checks that U1 is not a subsequence of U2 which is not the same as checking that U2 is a subsequence of U1. As the sets might just be completely unrelated which would be falsely dominated, as it happens in the first test

I think we need to check U2 is a subsequence of U1 explicitly which means checking std::includes(this, other) as in master. But for some reason std::includes(other, this) also works on the benchmarks but not with the new unit test. Also I think we need to check for equality, otherwise when U1 = U2 we may end up with neither label dominating, as it happens on

from cspy.

Hah yes it is confusing. Thanks for checking and the explanation! I hope I am wrong because the performance is much better with the master version (as opposed to patch90 version).

I am new to the area, but my interpretation from Righini and Salani, 2006 was that a label would dominate another label only if the partial path were a subset of the other partial path. Therefore, if you have two different sets of nodes, I would expect neither label to dominate. So, I would have expected the following to return false:

So, is it the case that if you have two different sets of partial paths you can say the label dominates the other for elementary paths?

Aside from the above, do we need to pass other.unreachable_nodes.cend() to std::equal as well? If other.unreachable_nodes is smaller, it may lead to a bug?

from cspy.

I am new to the area, but my interpretation from Righini and Salani, 2006 was that a label would dominate another label only if the partial path were a subset of the other partial path. Therefore, if you have two different sets of nodes, I would expect neither label to dominate. So, I would have expected the following to return false:

I think that's totally correct, in this case since unreachable_nodes are not comparable, the resources is what's making L2 dominate as res2[1] < res[1]. Similarly with the case when the unreachable sets are the same in

I tried making them as similar as possible, as if they are the same, the elementary check is not performed.

So, is it the case that if you have two different sets of partial paths you can say the label dominates the other for elementary paths?

If all the other criteria is satisfied, weight, and individual resource, yep!

What is done there is not only using the partial path but the unreachable nodes (which is just nodes that are in partial path + unreachable due to resources). It was introduced in Feillet et al. (2004), also referenced in the classic Irnich and Desaulniers (2005) (page 18 section titled ESPPRC).

Aside from the above, do we need to pass other.unreachable_nodes.cend() to std::equal as well? If other.unreachable_nodes is smaller, it may lead to a bug?

You're right here, I didn't know that std::equal allowed that. That'd be safer.

from cspy.

So, is it the case that if you have two different sets of partial paths you can say the label dominates the other for elementary paths?

If all the other criteria is satisfied, weight, and individual resource, yep!

Ok cool. I was thinking about this incorrectly. Page 18 in your source helped me understand it, thanks! Feel free to close this. Your unit test looks good to me and the code looks good (other than adding that part to std::equal).

from cspy.

Sweet, thank you very much for checking!

from cspy.

I accidentally posted this in #96 , but I meant to post it here, I am going to delete that comment and repost here.

Hey @torressa, I hit an example with the wrong result and I think this dominance check is not correct for elementary... at least when you have negative costs (or negative resource consumptions).
Here is a small example showing incorrect output:

max_res = [100]
min_res = [0]

H = DiGraph(directed=True, n_res=1)
H.add_nodes_from(['Source', 1, 2, 3, 4, 'Sink'])
H.add_edge('Source', 1, res_cost=[1], weight=1)
H.add_edge('Source', 2, res_cost=[1], weight=1)
H.add_edge('Source', 4, res_cost=[1], weight=100)
H.add_edge(1, 3, res_cost=[1], weight=10)
H.add_edge(1, 'Sink', res_cost=[1], weight=1)
H.add_edge(2, 3, res_cost=[1], weight=5)
H.add_edge(2, 'Sink', res_cost=[1], weight=1)
H.add_edge(3, 1, res_cost=[1], weight=-10)
H.add_edge(3, 2, res_cost=[1], weight=-100)
H.add_edge(4, 3, res_cost=[1], weight=1)

# The optimal path should be ['Source', 1, 3, 2, 'Sink']
# -88.0
bidirec = BiDirectional(H, max_res, min_res, elementary=True, direction="forward")
bidirec.run()
print(bidirec.path)
print(bidirec.total_cost)

This returns the wrong result because the label with partial path L1=(Source, 2, 3) dominates the label with partial path L2=(Source, 1, 3).

There are no resources and L1.cost = 6 < L2.cost = 11. However, if we were able to expand L2 we would have been able to hit the large negative value link (3,2,-100) which is needed for the optimal path.

Based on an example like this, I don't see how we can prune elementary paths based on dominance checks. With elementary, the partial path matters; e.g., L1 cannot expand into any paths that visit node 2 for instance. If the link weights are only positive, that would be fine because there would be no reason for L2 to expand to node 2. Unfortunately, if there are links that are negative, we don't know whether the label can expand into a state with better cost until it's completely expanded.

Am I missing anything?

from cspy.

Aha! That's interesting!
This goes back to what we were talking about before with unrelated partial paths.
I think it's clearer if we write the check like this (edit going back full circle to your first comment #94 (comment))

  if (params_ptr->elementary && unreachable_nodes.size() > 0 &&
      other.unreachable_nodes.size() > 0) {
    // check unreachable_nodes is a subsequence of other.unreachable_nodes
    if (std::includes(
            other.unreachable_nodes.cbegin(),
            other.unreachable_nodes.cend(),
            unreachable_nodes.cbegin(),
            unreachable_nodes.cend())) {
      // Dominated cause all conditions are satisfied
      return true;
    } else {
      return false;
    }
  }
  return true;

This fixes the example as neither label would dominate but leads to a massive performance decrease (for benchmarks which are all positive costs).
I think this is a special case as we have a few negative cost cycles. I'll have a think about this.

from cspy.

Yes, sadly a big performance hit :(. I think we also have to do this if there are negative resource consumptions as well. You could envision a similar scenario.

And yes, that code makes sense to me.

from cspy.

Just for sanity I've rewritten the elementary check explicitly as in the paper.
Seems to agree with the previous super slow case. I've added a check to not use elementary logic if no negative cost cycles are found, which I think is OK.

from cspy.

Reverted back again as it the set of unreachable nodes is more efficient (don't have to loop over all nodes dominance check).

I'm just working on some other bits to speed things up (motivated by Ruslan's answer in or.stackexchange). Adding the efficient labels as described (attempted in runDominanceEff). This keeps the labels sorted per node, so joining procedure can be stopped early (stills needs checking).
Also #78 might be worth a shot.

Also getting it to work on VRPy (adding non-elementary route handling was pretty essential anyway), after that I'll release.

from cspy.