<p>Building on the comment by @a3nm, this can be coded directly as a Network Flow problem (or Max Flow problem), and then solved using the Fork-Fulkerson algorithm or an equivalent Linear Program.</p>
<p><strong>Background</strong>
In a basic network flow problem, you have a directed graph with a source <span class="math-container">$s$</span> and a sink <span class="math-container">$t$</span>, where <span class="math-container">$s$</span> only has outgoing edges and <span class="math-container">$t$</span> only has incoming edges. The source <span class="math-container">$s$</span> produces units of &quot;flow&quot; which flow along the directed edges of the graph from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>. Except for <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, flow is conserved at all other nodes so that the flow coming in is equal to the flow coming out of the node. The total flow leaving <span class="math-container">$s$</span> must be equal to the total flow entering <span class="math-container">$t$</span>. For every edge in the graph you can assign it a  lowerbound and a non-negative upperbound on the amount of flow that must pass through the edge. The Ford-Fulkerson algorithm returns the flow through the network if it is possible to satisfy all the constraints.</p>
<p>The key difference between the way Network Flow problems are usually set up and the problem you have presented is that in flow problems the upper/lower bounds are on the edges rather than the nodes, but constraints on the nodes can be expressed as constraints on edges by adding source and sink nodes.</p>
<p><strong>Solution</strong>
For your problem, create a source node <span class="math-container">$s$</span> and a sink node <span class="math-container">$t$</span>. For every supply node <span class="math-container">$a \in A$</span>, create a directed edge from <span class="math-container">$s$</span> to <span class="math-container">$a$</span>. For every demand node <span class="math-container">$b \in B$</span>, create a directed edge from <span class="math-container">$b$</span> to <span class="math-container">$t$</span>. Connect the nodes between <span class="math-container">$A$</span> and <span class="math-container">$B$</span> as they are in your bipartite graph. Now for each edge from <span class="math-container">$s$</span> to a supply node <span class="math-container">$a$</span>, give it the lowerbound corresponding to the supply of <span class="math-container">$a$</span>. Similarly for the edges from <span class="math-container">$B$</span> to <span class="math-container">$t$</span>. For all other edges (those from <span class="math-container">$A$</span> to <span class="math-container">$B$</span>), set their lower bounds to 0. Now for all edges in the graph, set the upperbound to infinity.</p>

CC BY-SA 4.0
2022-10-26T07:58:47.953Z
2022-10-26T07:58:47.953Z
B A
<p>Given a set of distinct nodes (<span class="math-container">$A \cup B$</span>) one set represents nodes with a supply (<span class="math-container">$supply(a), a \in A$</span>) and the other represents nodes with a demand (<span class="math-container">$supply(b), b \in B$</span>). In a bipartite graph I am looking for a subset of edges with weights resembling the units transferred from <span class="math-container">$a \in A$</span> to <span class="math-container">$b \in B$</span>, such that every demand is satisfied. (Sum of all demands and supplies are equal). The graph is not necessarily complete, but each <span class="math-container">$a \in A$</span> has at least one edge to any <span class="math-container">$b \in B$</span>.</p>
<ol>
<li>Is there a term for this problem in graph theory? It is not a matching since a node <span class="math-container">$a \in A$</span> could fill the supply for more than one node <span class="math-container">$b \in B$</span>.</li>
<li>Is there a known solution algorithm for this problem?</li>
<li>Is the produced solution optimal?</li>
</ol>

CC BY-SA 4.0
2022-10-17T16:10:41.500Z
This is reminiscent of a flow problem (https://en.wikipedia.org/wiki/Maximum_flow_problem), coded as a bipartite graph with directed edges from the supply nodes to the demand nodes annotated by their capacity, and edges from the source to the left nodes (with capacity the maximal supply) and edges from the right nodes to the sink (with capacity the requested demand). If it is not this, could you explain how your problem is different?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-10-17T20:02:59.223Z
@a3nm that actually sounds like a good model. I will read up on flow problems tomorrow and try to model it. Thanks!!
Bernd Strehl
CC BY-SA 4.0
2022-10-17T21:17:07.903Z
Have  you looked at the assignment problem or b-matching problems? Or network flow?
Chandra Chekuri
CC BY-SA 4.0
2022-10-18T18:38:15.883Z
@a3nm if you propose this as an answer I will gladly accept.
Bernd Strehl
CC BY-SA 4.0
2022-10-18T19:52:18.257Z
This is the special case of the Hitchcock problem (https://en.wikipedia.org/wiki/Transportation_theory_(mathematics)#Hitchcock_problem) with 0/1 (or 0/$\infty$) costs.  Also called the [transportation problem](https://towardsdatascience.com/operations-research-in-r-transportation-problem-1df59961b2ad).  The special case of 0/1 costs probably has its own name as well.
Neal Young
CC BY-SA 4.0
2022-10-19T10:34:09.067Z
I'll let @NealYoung post as his point is more specific than mine!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-10-19T20:12:51.947Z
@NealYoung Thanks for referring me to that problem. I haven't heard about it so far.
Bernd Strehl
CC BY-SA 4.0
2022-10-26T08:01:51.627Z
When you ask whether the solution is optimal, optimal in terms of what? The problem is described vaguely, but sounds like a decision problem instead of an optimization problem as it is currently written.
B A
<graph-theory><graph-algorithms>
Solution for a bipartite demand and supply graph
Bernd Strehl
# Solution for a bipartite demand and supply graph

(Asked by: username_0 on 2022-10-17)

Given a set of distinct nodes ($A \cup B$) one set represents nodes with a supply ($supply(a), a \in A$) and the other represents nodes with a demand ($supply(b), b \in B$). In a bipartite graph I am looking for a subset of edges with weights resembling the units transferred from $a \in A$ to $b \in B$, such that every demand is satisfied. (Sum of all demands and supplies are equal). The graph is not necessarily complete, but each $a \in A$ has at least one edge to any $b \in B$.

1. Is there a term for this problem in graph theory? It is not a matching since a node $a \in A$ could fill the supply for more than one node $b \in B$.
2. Is there a known solution algorithm for this problem?
3. Is the produced solution optimal?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: This is reminiscent of a flow problem (https://en.wikipedia.org/wiki/Maximum_flow_problem), coded as a bipartite graph with directed edges from the supply nodes to the demand nodes annotated by their capacity, and edges from the source to the left nodes (with capacity the maximal supply) and edges from the right nodes to the sink (with capacity the requested demand). If it is not this, could you explain how your problem is different?  
> **username_0**: @a3nm that actually sounds like a good model. I will read up on flow problems tomorrow and try to model it. Thanks!!  
> **username_2**: Have  you looked at the assignment problem or b-matching problems? Or network flow?  
> **username_0**: @a3nm if you propose this as an answer I will gladly accept.  
> **username_3**: This is the special case of the Hitchcock problem (https://en.wikipedia.org/wiki/Transportation_theory_(mathematics)#Hitchcock_problem) with 0/1 (or 0/$\infty$) costs.  Also called the [transportation problem](https://towardsdatascience.com/operations-research-in-r-transportation-problem-1df59961b2ad).  The special case of 0/1 costs probably has its own name as well.  
> **username_1**: I'll let @NealYoung post as his point is more specific than mine!  
> **username_0**: @NealYoung Thanks for referring me to that problem. I haven't heard about it so far.  
> **username_4**: When you ask whether the solution is optimal, optimal in terms of what? The problem is described vaguely, but sounds like a decision problem instead of an optimization problem as it is currently written.  

---

## 1 answers

### Answer by username_4 on 2022-10-26. Score: 1 | Accepted answer

Building on the comment by @a3nm, this can be coded directly as a Network Flow problem (or Max Flow problem), and then solved using the Fork-Fulkerson algorithm or an equivalent Linear Program.

**Background**
In a basic network flow problem, you have a directed graph with a source $s$ and a sink $t$, where $s$ only has outgoing edges and $t$ only has incoming edges. The source $s$ produces units of "flow" which flow along the directed edges of the graph from $s$ to $t$. Except for $s$ and $t$, flow is conserved at all other nodes so that the flow coming in is equal to the flow coming out of the node. The total flow leaving $s$ must be equal to the total flow entering $t$. For every edge in the graph you can assign it a lowerbound and a non-negative upperbound on the amount of flow that must pass through the edge. The Ford-Fulkerson algorithm returns the flow through the network if it is possible to satisfy all the constraints.

The key difference between the way Network Flow problems are usually set up and the problem you have presented is that in flow problems the upper/lower bounds are on the edges rather than the nodes, but constraints on the nodes can be expressed as constraints on edges by adding source and sink nodes.

**Solution**
For your problem, create a source node $s$ and a sink node $t$. For every supply node $a \in A$, create a directed edge from $s$ to $a$. For every demand node $b \in B$, create a directed edge from $b$ to $t$. Connect the nodes between $A$ and $B$ as they are in your bipartite graph. Now for each edge from $s$ to a supply node $a$, give it the lowerbound corresponding to the supply of $a$. Similarly for the edges from $B$ to $t$. For all other edges (those from $A$ to $B$), set their lower bounds to 0. Now for all edges in the graph, set the upperbound to infinity.


---

