Cycle detection in commodity_graph detecting too many cycles

[idelder]

Under certain circumstances a combinatorial problem arises in cycle detection. Example network below:

If I got this right (great way to kill an hour), there are 81 simple cycles through this network (doesn't visit any commodity twice)

length	combinations	example
6	36	1A2B3C'
5	0	-
4	36	1A2B'
3	0	-
2	9	1A'
total	81

Put a few of these blocks together and it quickly explodes. We had a case where so many cycles were being output to the log file that the log file size hit 56 GB, couldn't be opened, and slowed the model run to a crawl.

Low priority but possible fixes:

1. Check how many simple cycles were found. If it is very large, then just log "N cycles detected [...]". This doesn't avoid the slowdown of actually finding all those cycles though, which I haven't tested yet.
2. Have a counter check on the cycle iteration block. Log a few cycles then log like above.
3. Have a configuration option to disable just the cycle check, in case the detection itself is very slow and should be skipped but we still want orphan detection.

[ParticularlyPythonicBS]

maybe a fail early so that it exits after first detected cycle? I figure those who care about cycles care about all of them and those who don't have just one log to ignore

[idelder]

Yeah I'd be fine with that

[jeff-ws]

A quick drive-by. We got cycle detection 'for free' when we put the network stuff into Network X pkg for graphing. It was an add-on at the time. The one case where you really want it is if there are any cost arcs that are negative. Possibly via linked techs or in some area where modeler might be clever and trying to credit the capture or generation of something with a negative variable cost. (or fixed ??). Anyhow, those situations can cause havoc if there is any loop with a net negative cost for semi-obvious reasons. There may be others...not sure would have to think about it if there are any dangers absent a negative cost---in theory there should be no "additional" unneeded activity in a demand satisfaction model with all positive costs, but it may still be nice to know about loops (if it doesn't bust the construction). So, as you go forward, perhaps screening the loops for any that involve tech with negative cost would be 1 filtering idea....

[jdecarolis]

Getting caught up on this thread, and looking to close out this issue for the Temoa v4 release.

First question, for my own edification @jeff-ws: do we get cycle detection for free because the cycle includes one of the orphan types described in your commodity network notes?

Second question, any consensus on how we resolve? This issue is clearly a problem for the CANOE team so we should resolve.
Options include:

1. Detect cycles but exit after n detections
2. Specifically focus on cycles with negative cost coefficients
3. Add option in config file to disable cycle check

My only concern with #1 is what if I want to have model report all cycles? Thoughts @idelder @jeff-ws @ParticularlyPythonicBS ?

[jeff-ws]

As mentioned, we get the detection for free through the use of networkx, which is a bridge to graphing. I saw that it had cycle detection, knew we had problems with that, so I roped it in. It still remains and you can see it in commodity_graph.py near the end of the file. It became clear that there are/were some intentional cycles in the graphs, so it logs them as info level items instead of warnings, etc.

If you want to "nip it in the bud" if it stumbles into a graph with millions (!!?? separate issue below) of loops, it would be a 1-liner to put in a counter limit in there such that if it finds 999 cycles, it stops reporting. From the networkx documentation, it appears that the cycle detection runs a Generator which is good news, because it isn't pre-computing all of the loops or storing them in memory, so it should be safe to abandon by breaking the loop, probably with a log comment along the lines of "more than x loops detected, abandoning loop detection... (and why have you designed such a beast? ;). )"

Aside: I find the graph at the top a little confusing misleading. What is described as "use" and "recycle" is actually multiple technologies, right? That's the only way you get into this. So there are 18 Techs in there T[1, A], T[1, B], T[2, A], ... T[A, 3], T[C,3]. That seems overly "flexible" unless it is very important to model all of of those feedback loops, and quite burdensome in the solve process. Are there not reasonable simplifications by combining commodities or such?

[idelder]

I think a config option to turn off cycle detection but keep other network checks on makes the most sense. Easiest and most robust option.

This problem emerged for us in materials supply chains where you have lots of different materials worming their way through different battery chemistries. It's a niche edge case so I wouldn't want to spend too much effort compensating for it.

[jeff-ws]

If the config is easily accessible within the file, then adding it as a config object, that seems like a good improvement.

From a design perspective, it would still be best to put in a trigger to break the loop and stop reporting after N cycles simply because--as we have seen--you can lock up execution in an odd way in certain parasitic cases. And it ways that might be difficult to T/S to newer users. That patch is just a simple counter with breakout.

[idelder]

I agree with that. Much better to have a prompt and clear warning than just a hanging model