Solve the revenue issue

[jwalzberg]

Description

Including revenues in each life cycle step seems to prevent the model from choosing pathways that seem to make sense looking at costs and revenues data in the .yaml scenario files. As the decision is made on the lump costs and revenues (and not at each life cycle step independently) this could create this behavior.

Data Solution

Remove costs and revenues data for any unecessary step where we know the step is profitable and will not be varied in our sensitivity analysis (since the pathway decision will not be affected by those steps). At the very least, this would make understanding the issue easier... This solution should be implemented by changing the scenario yaml files directly.

@rjhanes and @tapajyoti-ghosh I can take on the proposed solution above. Let me know if you have any thoughts or comments before I do.

Code Solution

The issue is likely caused by the cost adjustment factor being non-zero for many of the scenarios that include positive revenues. The cost adjustment is applied to all edges in the network, and all process costs are increased by the same amount. While the cost adjustment factor preserves the relative cost of all processes, it does not preserve the relative costs of all pathways. Shorter pathways that contain fewer edges will have fewer cost adjustment factors added, while longer pathways will have more cost adjustment factors added.

A linear pathway:

[in use] -A-> [uninstall] -B-> [landfill]

• Original cost = A + B
• Adjusted cost = (A + f) + (B + f) = A + B + 2f
• Pathway cost increase = 2f

A closed-loop circular pathway:

[in use] -A-> [uninstall] -B-> [disassembly and sorting] -C-> [secondary production]

• Original cost = A + B + C
• Adjusted cost = (A + f) + (B + f) + (C + f) = A + B + C + 3f
• Pathway cost increase = 3f

Circular pathways will, in general, contain more edges than linear, thus circular pathways with non-zero revenues are penalized.

The cost adjustment factor is applied in the first place so the path-finding algorithms built into networkx function properly. These algorithms cannot handle negative edge weights (costs).

There's a few things to try. In order from largest to smallest likelihood of success:

• Tweak the shortest-path code such that pathways are compared based on the unadjusted pathway costs. This would require using the same pathfinding algorithm, and adjusting the weighted lengths down by the cost adjustment factor times the number of edges in each pathway.
• Duplicate and modify a pathfinding algorithm from networkx such that negative edge weights are allowed.
• Explore alternate network packages, newer versions of networkx, and alternate algorithms in networkx

[rjhanes]

Three potential options for replacement shortest-path algorithms, in networkx version 3.5:

• goldberg_radzik
• bellman_ford_predecessor_and_distance
• johnson

I tested on the baseline scenario CostGraph to evaluate timings. GR and BFPD both ran effectively instantaneously. GR only works off source nodes; BFPD can take both source and target nodes. Johnson takes ~26 seconds to run on the national scale costgraph because it finds shortest paths between all node pairs in the network, but would only need to be run once per timestep as opposed to once per component-timestep.

Next up: Test on high-revenue scenarios (real or fake) to try and force an error. Docs for BFPD did indicate that while it can handle negative EDGE weights, negative PATH weights are a strict no-go because of the potential for path weights that go to negative infinity. Unclear yet if defining both source and target nodes for BFPD is a way around that.

[rjhanes]

Progress update: I'm using a combination of the current pathfinding algorithm (astar) with logic that checks for negative cycles and uses alternate logic to still locate shortest paths. The alternate logic is likely much slower than the built-in shortest path algorithms, hence the negative cycle check.

Currently testing on high-revenue scenarios (203, 209, 215, etc) to check that all edge cases in the glass study have been caught.

Next steps after local testing is to execute runs on Kestrel and go through the results with a fine tooth comb to make sure the updated logic is executing as we expect.

[rjhanes]

Progress update: In testing the combo logic described in the previous note, I'm seeing that the non-shortest-path algorithm takes 25-75 seconds per path to find on my laptop. This is workable (at least it's running) but I think can be improved upon, to the benefit especially of later simulation years where both BOL and EOL paths need to be found.

I'm going to test the johnson algorithm to see if it can deal with negative path weights (it's not specifically discussed in the documentation). If it can, then we can run it once per timestep and pull out paths from the data structure it creates where negative path weights prevent the use of the standard shortest path algorithm. I suspect this will be much faster overall.