Go With The (Nework) Flow, Part I

Some preliminaries:

(1) I couldn't resist posting a link to this New York Times piece about eHarmony, et al. The "Algorithms of Love" in the headline alone made it worth it. (By the way, I love it when copy editors choose to force "EHarmony" and the like when these ridiculously capitalized words come up at the beginning of a sentence. It's like a little "screw you and your trademark" from the folks for whom sloppy capitalization is almost an affront. Speaking of which, sorry for the up-style headlines on this blog. I abhor up style, but I somehow backed myself into this corner and am not about to back down now.)

(2) My friend Rachel just let me know that you can hear David Foster Wallace reading "The View from Mrs. Thompson's" from Consider the Lobster on "KCET Podcast: Hammer Conversations" (Episode 16), which is available on iTunes. I listened to it this evening, and it's terrific. Copy snobs will love the little explanation about his use of em dashes, but anyone will almost certainly be moved by the story. Plus Wallace's reading voice matches his "authorial voice" really well, in my opinion.

OK, on to the main event. I mentioned a couple posts ago that I hope to use this space as a sort of whiteboard for trying out ideas, and I'm expecting to need such a space in the coming weeks. I'm getting ready to start working on the algorithms for matching material offers and requests in GENIUS and as such am learning about solving network flows problems. Wanna learn a little bit about them with me? If so, read on.

We'll start with the basic first lesson, which I sat through just the other day. The gist of flow networks is that you've got a collection of nodes with material traveling between them along directed connections called arcs. Nodes are either sources (supply nodes that create material), sinks (demand nodes that consume material), or transshipment nodes that simply send a material along.

What we try to solve for in these problems is an optimal flow vector, which is just a fancy name for a long list that says how much of the material flows along each arc. The vector is optimal in the sense that it represents the flow for which the problem constraints are met in the cheapest way possible (there's a cost associated with moving a unit of material along each arc). The problem constraints are flow bounds (upper and lower limits on how much flow must move along an arc) and conservation of flow, which says that the outflow minus the inflow at each node must equal either zero (for transshipment nodes) or the supply or demand of the node (for sources and sinks, respectively). The second set of constraints are also called divergence equations.

Brief mathematical note for those who are interested: network flow problems are special cases of linear programs, albeit much easier to solve ones (via the network simplex method, rather than general linear programming's modifier-less simplex method). There are also, apparently, special algorithms for solving various special-case problems that can be posed as network flow problems, including Euler's famous Konigsberg Bridge Problem.

What does all this have to do with the nuclear fuel cycle? Stay tuned as I try to figure that out.