cspy.BiDirectional (monodirectional)

[saahaand]

I am using monodirectional "forward" algorithm to solve Elementary shortest path problem with capacity constraints to do branch and price. This algorithm is supposed to give the exact solution meaning that finding the most negative cost elementary path (reduced cost);however, I noticed that by increasing the number of nodes in graphs (usually >20) sometimes it finds a suboptimal path. Here is what happens in my example: The optimal path is ["Source", 1, 65, 69 ,5, 9, "Sink"] which its cost is -23.42. However, the algorithm finds the path ["Source", 1, 5, 65, 69, 9, "Sink"] whit the cost of -22.31. (In most cases the same nodes with different orders like shown in the example but also sometimes totally different paths).

Note that this example happened in solving the root node before doing any branching; hence, the problem cannot be because of any bug in my branching code.

I wanted to ask if it is a known issue?

[torressa]

Hi @saahaand! Thanks for reporting this. It is possible, what version are you using? I worked on a bugfix related to this (https://github.com/torressa/cspy/issues/94) on the latest version. Also, a similar issue was reported in https://github.com/torressa/cspy/issues/98 but never got properly investigated.

If you are, do you mind sharing a script + data to reproduce this issue? You can save the networkx graph using nx.write_graphml.

[torressa]

@saahaand any more details on this?

[saahaand]

Hi @torressa

Thank you for your reply and I am sorry for the delay. As you suggested I saved the graph using "nx.write_graphml". It was not supporting numpy array, so I had to change the "res_cost" attribute of graph in cspy from numpy array to float to be able to use "nx.write_graphml". Here, I attach the file.

Moreover, I have max_res, min_res = [50], [0] as my parameters for cspy bidirectional "forward" algorithm. I also set "elementary"=True, as I am solving elementary shortest path problem with resource constraint.

As mentioned above the optimal path is ["Source", 1, 65, 69 ,5, 9, "Sink"], while bidirectional "forward" finds ["Source", 1, 5, 65, 69, 9, "Sink"].

Thank you again and please let me know if you need any further file or information that I might have missed to report. Graph_check_file.txt

[torressa]

I cannot replicate this. Please ensure that you are on the latest version 1.0.2. Check

python3 -m pip list | grep cspy

Rounding the edge weights to different decimal places causes very different paths. I am getting the optimal path pretty consistently when rounding to 3 or more decimal places and not with the cost you pointed out.

# 2 dp
alg.path=['Source', '9', '5', '69', '65', '1', 'Sink']
alg.total_cost=-23.230000000000018

# 3 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.222999999999985

# 5 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.223780000000005

# 10 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.223770066100002

[torressa]

There's actually something weird going on with direction="both".

[saahaand]

Thank you. I will try your suggestion for "forward" direction and let you know.

Yes , you are right about "both" and "backward" version. I had already noticed some problem with several other instances when I set direction as "both" or "backward", but "forward" was performing well until I noticed the above example.

For the above example by setting direction as "both", I get the path ['Source', 89, 1, 5, 9, 'Sink'], which is definitely not the optimal path.

[torressa]

There's actually something weird going on with direction="both".

Yes , you are right about "both" and "backward" version. I had already noticed some problem with several other instances when I set direction as "both" or "backward", but "forward" was performing well until I noticed the above example.

The reason for this is because your edges with resource costs of 0 are violating assumption 1 of the algorithm (they are not strictly monotone): https://torressa.github.io/cspy/ref.html#pre-requirements You can either

1. change this first resource to a dummy monotone resource (count nodes, so all edges have res_cost of 1) and add your resource as a secondary resource.
2. make your resource monotone

[saahaand]

I cannot replicate this. Please ensure that you are on the latest version 1.0.2. Check

python3 -m pip list | grep cspy

Rounding the edge weights to different decimal places causes very different paths. I am getting the optimal path pretty consistently when rounding to 3 or more decimal places and not with the cost you pointed out.

# 2 dp
alg.path=['Source', '9', '5', '69', '65', '1', 'Sink']
alg.total_cost=-23.230000000000018

# 3 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.222999999999985

# 5 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.223780000000005

# 10 dp
alg.path=['Source', '1', '65', '69', '5', '9', 'Sink']
alg.total_cost=-23.223770066100002

@torressa Thank you very much. Rounding the edge weights to a certain decimals, fixed the problem. Now, I get the optimal solution. I really appreciate your help.

[torressa]

There's actually something weird going on with direction="both".