PSOLGENT can only find paths for nodes in sorted order

[dvbuntu]

Describe the bug PSOLGENT is unable to recover paths when the node order taken (i.e. the edges) is not in the sorted order of the node names themselves. This is because when we convert the node scores to a path, there is a single fixed order or nodes (the sorted one). So pattern [1, 0, 0, 1, 1, 1] always refers to path Source -> 3 -> 4-> Sink, and never Source -> 4 -> 3 -> Sink. This severely limits what constrained paths can be found.

From the PSOLGENT paper, it's not clear that they address this. At the end of section 4.1, they mention that different orders "could be examined", but it's as though it's not a major concern to them. I might be missing some understanding of what exactly their variable neighborhood search accomplishes.

Either way, the cspy implementation doesn't seem to address this. Given a particular activation of nodes, there is a fixed set of edges produced, even if another ordering would be better (or feasible at all).

To Reproduce

from networkx import DiGraph
import numpy as np
from cspy import BiDirectional, PSOLGENT

## make a small graph, only Source->B->A->Sink is feasible
max_res, min_res = [10], [0]
H = DiGraph(directed=True, n_res=1)
H.add_edge("Source", 'A', res_cost=np.array([1]), weight=1)
H.add_edge('A', 'B', res_cost=np.array([9]), weight=1)
H.add_edge('A', 'Sink', res_cost=np.array([1]), weight=1)
H.add_edge('Source', 'B', res_cost=np.array([1]), weight=1)
H.add_edge('B', 'Sink', res_cost=np.array([1]), weight=1)
H.add_edge('B', 'A', res_cost=np.array([1]), weight=8)
bidirec = BiDirectional(H, max_res, min_res, seed=42, preprocess=False)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources) ## ok
pso = PSOLGENT(H, max_res, min_res, seed=42, preprocess=False)
pso.run() # works ok here
print(pso.path, pso.total_cost, pso.consumed_resources) ## ok

# change only name of a node
nx.relabel_nodes(H, {'A':'C'}, copy=False)
bidirec = BiDirectional(H, max_res, min_res, seed=42, preprocess=False)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources) ## still fine
pso = PSOLGENT(H, max_res, min_res, seed=42, preprocess=False)
pso.run() # unable to find path!

Expected behavior PSOLGENT should be able to find paths where nodes occur out of their sorted order.

Desktop (please complete the following information):

• OS: CentOS
• cspy 1.0.1
• networkx 2.5
• Python 3.8.5

Suggestions One approach would be to add another "position" to each node in the PSO. This second position would be use to determine the order of nodes when converting to a path. It could be arbitrary reals just like the "node activation" position value, and we would sort the nodes according to this 2nd learned value.

While I think this could work, this is just a hypothesis. The PSOLGENT paper doesn't mention anything like this. We'd be doubling the number of dimensions, which will slow things down.

I'm not sure how other PSO-type path finding schemes address this issue. It might be in the neighborhood search part of the paper that I haven't thought through fully. If there's an existing methodology, perhaps we should do that. If my above idea is untested in the literature, that might be an interesting research problem.

[torressa]

Hey! I'll merge the PR later today. This is a really good catch! I have no idea whether the second velocity dimension would work...

However, in the paper they kind off describe it in the paragraph just above section 4.2. Basically run a number of fixed local search iterations (or the number combinations of nodes whatever is smaller) to see if a different (feasible) ordering of the nodes of the sequence given by the pattern is better. For example, I've done this for GRASP here https://github.com/torressa/cspy/blob/bf82b8a5f9527b79df2ce5aca0b8ec903023984e/src/python/algorithms/grasp.py#L191 In the local search phase, https://github.com/torressa/cspy/blob/bf82b8a5f9527b79df2ce5aca0b8ec903023984e/src/python/algorithms/grasp.py#L137-L150 this is repeated this until the number of iterations exceeds max_localiter (yet another parameter) and typically stops after first improvement. I.e. break after the if-statement on line 146.

We can reuse this, or feel free to implement something similar.

[dvbuntu]

Perfect, I'll try to adapt this to PSOLGENT. Thanks for clarifying!

[dvbuntu]

Hmm, how well does that method work in GRASP? I ask because I have a small example I'm testing PSO with, but GRASP also fails (oddly enough in a different way). I haven't looked through the GRASP algorithm to understand if this just the nature of it, or a problem with the local search.

I adapted this local search to PSOLGENT, but get similar results to GRASP (in this case random whether it first goes to B or C, but then likes to go immediately to Sink). I'm still checking for bugs, but this approach doesn't seem to reliably solve this toy problem.

from networkx import DiGraph
import numpy as np
from cspy import BiDirectional, PSOLGENT

## make a small graph, shortest Source->C->B->Sink 
max_res, min_res = [10], [0]
H = DiGraph(directed=True, n_res=1)
H.add_edge("Source", 'C', res_cost=np.array([1]), weight=1)
H.add_edge('C', 'B', res_cost=np.array([1]), weight=1)
H.add_edge('C', 'Sink', res_cost=np.array([1]), weight=8)
H.add_edge('Source', 'B', res_cost=np.array([1]), weight=8)
H.add_edge('B', 'Sink', res_cost=np.array([1]), weight=1)
H.add_edge('B', 'C', res_cost=np.array([1]), weight=8)
bidirec = BiDirectional(H, max_res, min_res, seed=42, preprocess=False)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources) ## ok
gra = GRASP(H, max_res, min_res, preprocess=False)
gra.run()
print(gra.path, gra.total_cost, gra.consumed_resources) ## bad answer

[torressa]

Just pushed what I meant https://github.com/torressa/cspy/pull/80#issuecomment-868858578. Also removed the psolgent-defined attribute best_path as it saved resource-infeasible paths (mentioned here)

For the unit test, I modified the graph to actually force Source->B->A->Sink as Source->A/B->Sink were also feasible and minimal. Would like to come up with a better instance here to actually check the swapping is working as expected.