Some Flow Problems about gurobi-optimods HOT 6 CLOSED

network_flow might as well be public: it could make a good nup itself if there is more information we want to convey about the formulation

from gurobi-optimods.

Happy if we want to further split this into three issues, but thinking about the common formulation probably leads to a cleaner implementation.

from gurobi-optimods.

Yes such network flow problems certainly deserve a nup/nups. How exactly this should be realized in the backend? Many options, we should brainstorm a little before starting this. My current thinking is "simplicity first", but what exactly that means remains to be determined.

from gurobi-optimods.

In the short term I agree, simplicity first. It would be good to just implement various specific network flow problems without any dependency on one another.

Long term - as an educational tool it would be great to show a heirarchy of how various problems reduce to network flows, then each specific case can use the network flow nup as it's backend.

from gurobi-optimods.

Cool! Will split this into three at some point this week.

How exactly this should be realized in the backend?

In the backend complicated version, I was thinking of just having a single private network flow formulation for these problems nupstup._network_flow and then using the table above to formulate and solve the problem depending on the call.

# nupstup.min_cost_flow would return 
nupstup._network_flow(G, costs, capacities, demand, source, sink)
# nupstup.shortest_path
nupstup._network_flow(G, costs, [1 for _ in arcs], [1, 1], source, sink)
# max_flow returns (need to define V' for this one)
nupstup._network_flow(
    G,
    [-1 for e in edges if e[0] == source],
    capacities,
    None,
    source,
    sink,
    Vd=[n for n in nodes if n not in [source, sink]],
)

Except for min-cut where max-flow has to be run then we have to process the cutsets using the solution but this we will have to do anyway.

I think this sort of grouping would help maintenance, but yeah I agree it is a bit too much for the beginning.

from gurobi-optimods.

Closing as base functionality is already in; follow-up in #51.

from gurobi-optimods.