-
Notifications
You must be signed in to change notification settings - Fork 31
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Some Flow Problems #11
Comments
Happy if we want to further split this into three issues, but thinking about the common formulation probably leads to a cleaner implementation. |
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. |
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. |
Cool! Will split this into three at some point this week.
In the backend complicated version, I was thinking of just having a single private network flow formulation for these problems
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. |
|
Closing as base functionality is already in; follow-up in #51. |
Why this Nup?
Flow problems are present in many applications.
Particularly, the following share the same formulation (with some small changes):
All single source/sink.
Given a digraph$G=(V, E)$ , with source $s$ and sink $t$ , we can formulate these as follows:
Where$\delta^+(\cdot)$ ( $\delta^-(\cdot)$ ) denotes the outgoing (incoming) neighours, and
Does it fall under an existing category?
Graphs
What will the API be?
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.
The text was updated successfully, but these errors were encountered: