NLP solver

[snorfalorpagus]

Investigate writing a network linear programme based solver using GLPK.

See glpk/docs/graphs.pdf.

[snorfalorpagus]

NetworkX has a function for returning the "line graph" (what we were calling the dual) from an existing directional graph: https://networkx.github.io/documentation/latest/reference/generated/networkx.generators.line.line_graph.html

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('a', 'b') #  implicitly adds nodes
>>> G.add_edge('b', 'c')
>>> G.nodes()
['a', 'b', 'c']
>>> G.edges()
[('a', 'b'), ('b', 'c')]
>>> L = nx.line_graph(G)
>>> L.nodes()
[('a', 'b'), ('b', 'c')]
>>> L.edges()
[(('a', 'b'), ('b', 'c'))]

That's the hard bit done. Need to add the inputs+outputs onto the graph, then all the hidden arcs.

[jetuk]

There are some properties of the constraint matrix A that determine whether a problem is a NLP. I'll dig out the references but it something like each column containing only two entries (1 and -1). Essentially it is the network connectivity matrix.

I wonder if it is possible to transform the existing A matrix in to a NLP. This may be easier than building it from scratch? The pycllp solver constructs the A matrix directly. It ends up looking like this,

[[A1 I],
 [A2 0]]

in block form.

[snorfalorpagus]

Initial attempt is here: https://github.com/pywr/pywr/commit/a5e4f368f828f55f9723bbba9cf6946b7e305439

I did this a while back (200 commits ago!). I think this is workable although no idea what state the commited code is in. I've worked out the basics.

I think there might be some limitations, e.g. I don't think cross-domain conversion factors != 1 are possible.

[snorfalorpagus]

Another limitation of this is that there is no way to implement the aggegate nodes that limit flow over a group of nodes.

[jetuk]

We could have a mechanism for the solver to bail out if it detects something in a Model that it can't handle?

[snorfalorpagus]

We could have a mechanism for the solver to bail out if it detects something in a Model that it can't handle?

Yes. I thought about adding some sort of "capabilities" object to parameters/nodes, which the solver would check at the start. If it finds a capability it isn't aware of it would croak.

[jetuk]

Related to #702.