Conflict with the definition of label dominance

[Kuifje02]

Describe the bug A non optimal solution is returned in the following small example (for BiDirectional and Tabu)

To Reproduce Steps to reproduce the behavior:

#create graph
G = nx.DiGraph(directed = True,n_res=2)
G.add_edge("Source", 1, weight=10, res_cost=np.array([1,1]))
G.add_edge("Source", 2, weight=10, res_cost=np.array([1,1])) 
G.add_edge("Source", 3, weight=10, res_cost=np.array([1,1]))
G.add_edge(1, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(2, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(3, "Sink", weight=-10, res_cost=np.array([1,0]))
G.add_edge(3, 2, weight=-5, res_cost=np.array([1,1]))
G.add_edge(2, 1, weight=-10, res_cost=np.array([1,1]))

#resource limits
max_res, min_res = [len(G.edges()),2], [0,0]

#run algorithms
path_1 = cspy.Tabu(G, max_res, min_res).run()
path_2 = cspy.BiDirectional(G, max_res, min_res, direction="both").run()

#print paths
print(path_1)
print(path_2)

Expected behavior Both algorithms return ['Source', 1, 'Sink'] which has cost 0, and which consumes only 1 resource, while path Source-2-1-Sink is feasible (2 resources are consumed) and cheaper (cost -10).

[torressa]

Hi @Kuifje02! Cheers for another bug. The tabu algorithm doesn't give optimal paths, just resource feasible ones. I've just quickly checked, the networkx.astar_path (used in tabu) gives the same solution. The bidirectional algorithm however, should give the result you've stated. I'll dig into it. Also, contributions are very welcome!

[torressa]

Hey @Kuifje02, just had another thought about this. It's actually an interesting case. The label containing the Source-2-1-Sink path, say label_1, has a total weight of -10 and a total resource usage of [3,2]. The label containing the Source-1-Sink path, say label_2, has a total weight of 0 and a total resource usage of [1,0]. According to the definition of dominance in https://github.com/torressa/cspy/blob/1c29bff13f36764201b2b0d8049e983bc745c683/cspy/algorithms/label.py#L60 when these two labels are compared, label_1 does not dominate label_2, because even though the weight is lower, label_1.weight < label_2.weight, the resource usage is higher, all(label_1.res <= label_2.res) is not true. The other way around, label_2 does not dominate label_1 because even though the resource is lower, all(label_2.res <= label_1.res) and any(label_2.res <= label_1.res) is true, the weight is higher, label_2.weight <= label_1.weight is not true.

To overcome this, we can add another condition to the if statement saving the final labels: https://github.com/torressa/cspy/blob/1c29bff13f36764201b2b0d8049e983bc745c683/cspy/algorithms/bidirectional.py#L285 Saying something like neither labels dominate each other then pick the one that has the smallest weight.

[Kuifje02]

Yes that makes sense. I have checked how it is implemented in the pylgrim library (a python library for the elementary constrained shortest path). I am not sure I understand as I don't see such a criteria in his domination function : https://github.com/ToonWeyens/pylgrim/blob/45ac035f38c33cba4e55180480316b1a442b15cd/pylgrim/ESPPRC.py#L321. Maybe I haven't spend enough time thoroughly reading the code !

ps : I would be happy to contribute if I manage to find some time :)

[torressa]

Yeh, they did the same thing, just more elegantly, it's the standard definition for dominance (from Righini and Salani, 2006):

In pylgrim, a label b dominates a label a if and only if not a[0] < b[0] and not any(a[1] < b[1]). I think index 0 is the cost/weight and index 1 contains an array with resource consumptions. The converse statement would be, label b dominates a label a if both b[0] <= a[0] and all(b[1] <= a[1]) with at least one of the equalities is strict (for any resource in index 1). This is what I tried to write in my function, however, with the single return it all seems pretty confusing (and probably misses wrong). Additionally, when you're traversing the graph backwards the inequalities for resources get flipped. Anyway, will change to make it less confusing.

[torressa]

Changed the definition of dominance one closer to the one in pylgrim (hence more elegant). This wasn't enough unfortunately, since the definitions were equivalent neither label dominates. However, if you flip the direction and check the dominance again, this flips the inequality for resources and you get a solution that has a lower cost with a still-feasible but higher resource consumption.

[torressa]

Closing for now, but needs further testing.