Some Flow Problems

[torressa]

Why this Nup?

Flow problems are present in many applications. Particularly, the following share the same formulation (with some small changes):

• [x] Min cost flow.
• [x] Shortest path problem.
• [x] Max flow/min cut

All single source/sink.

Given a digraph $G=(V, E)$, with source $s$ and sink $t$, we can formulate these as follows:

$$ \begin{alignat}{2} \min \quad & \sum{(i, j) \in E} c{ij} x{ij} \ \mbox{s.t.} \quad & \sum{j \in \delta^+(i)} x{ij} - \sum{j \in \delta^-(i)} x_{ji} = bi & \forall i \in V' \ & 0 \leq x{ij} \le B_{ij} & \forall (i, j) \in E \ \end{alignat} $$

Where $\delta^+(\cdot)$ ( $\delta^-(\cdot)$ ) denotes the outgoing (incoming) neighours, and

$$ b_i = \begin{cases} D & \text{if } i = s\ -D & \text{if } i = t \ 0 & \text{ow} \end{cases} $$

Problem	$V'$	$D$	$B_{ij}$	$c_{ij}$
1.	$V$	$\geq 0$	$\geq 0$	$\geq 0$
2.	$V$	$=1$	$=1$	$\geq 0$
3.	$V\setminus\{s,t\}$	n/a	$\geq 0$	$=-1$ if $i=s, j\in\delta^+(s)$, $0$ ow

Does it fall under an existing category?

Graphs

What will the API be?

nupstup.min_cost_flow(G, costs, capacities, demand, source, sink)
nupstup.max_flow(G, capacities, source, sink)
nupstup.min_cut(G, capacities, source, sink)
nupstup.shortest_path(G, costs, source, sink)

Additional context

Well-known graph problems, so graph theory terminology is fine.

There are many real-world applications and other graph problem transformations for these, so would be good to have some of these in there as well.

Problem 1 -> Minimum weight bipartite matching Problem 3 -> Maximum cardinality bipartite matching, closure problem

If we go up another dimension and add $x_{ij}^k$ (also $D^k$) for a commodity $k$ we can model multicommodity flows with this same formulation as well.

[torressa]

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

[rluce]

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.

[simonbowly]

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.

[torressa]

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.

[simonbowly]

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

[rluce]

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