<p>This is a standard variant (if not <em>the</em> standard variant) of the minimum-cost flow problem.  The "flow requirements" are sometimes called <em>balance conditions</em> and sometimes called <em>vertex supplies/demands</em>.  It can be solved in polynomial time using any number of algorithms.</p>

<p>In particular, you can reduce to the single-source single-target variant in polynomial time as follows:</p>

<ul>
<li>Compute a conservative upper bound $M$ on the cost of any flow in your network; for example, let $M = \sum_e cap(e)\cdot |cost(e)|$.  Alternatively, treat $M$ as a symbolic infinite value.</li>
<li>Add new nodes $s^*$ and $t^*$.</li>
<li>Add arcs $s^*\to s$ and $t\to t^*$ with infinite capacity and zero cost.</li>
<li>For every node $v_i$ with $r_i&gt;0$, add an arc $s^*\to v_i$ with capacity $r_i$ and cost $-M$.</li>
<li>For every node $v_i$ with $r_i&lt;0$, add an arc $v_i\to t^*$ with capacity $-r_i$ and cost $-M$.</li>
<li>Set all vertex requirements to zero.</li>
</ul>

<p>The minimum-cost feasible flow from $s^*$ to $t^*$ in this modified network saturates every arc $s^*\to v_i$ and $v_i\to t^*$, and the remaining arcs carry the minimum-cost flow from from $s$ to $t$ in the original network that meets all the flow requirements.</p>

CC BY-SA 3.0
2013-05-18T01:41:51.603Z
I am not sure about the reduction to the original problem. This solution seems to just inject some required flow externally. If $s^*$ and $t^*$ are removed, the saturation effect for every node will be gone and also the flow conservation will not be held any more because an incoming flow of $r_i$ is removed from every node.
Javad
CC BY-SA 3.0
2013-05-17T18:43:05.483Z
2013-05-17T18:43:05.483Z
Jeffε
<p>Consider the standard minimum-cost flow problem presented <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem#Definition" rel="nofollow">here</a>. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and the target $t$) as follows:
$$\sum\limits_{w \in V } {f({v_i},w) = \sum\limits_{w \in V} {f(w,{v_i}) = } {r_i}} ,\forall {v_i} \in V - \{ s,t\},$$
where $r_i$ is called vertex $v_i$ flow <em>requirement</em> (is there a standard term for it?). Please note that this problem is single-commodity and it is different from the <a href="http://en.wikipedia.org/wiki/Multi-commodity_flow_problem" rel="nofollow">multi-commodity flow problem</a>.</p>

<p>Moreover, consider that all the capacities, costs, flows, and requirements are non-negative integers. Is there a well-known algorithm to solve this problem in polynomial time? If this is an NP-Complete problem, what's the fastest known algorithm and the approximation method to solve it?</p>

CC BY-SA 3.0
2013-05-17T02:34:27.383Z
I was thinking of duplicating every intermediate node $v_i$ to $v_i^1$ and $v_i^2$ and adding an edge from the former one to the latter one and setting the capacity of the edge as $d_i$ and the cost as a large negative number which is actually a reward for maximizing the flow to the original node. Does this idea work especially because of adding a negative cost?
Javad
CC BY-SA 3.0
2013-05-17T03:09:07.720Z
It's possible to solve this problem using Linear Programming. E.g., by duplicating vertices (as in your comment), and connecting t to s, you can restate this problem as a min cost circulation problem, in which the amount of flow on every edge is bounded from above and below. The set of such circulations forms an integral polytope. Thus LP will give you an integral solution.
Yury
CC BY-SA 3.0
2013-05-18T03:29:11.723Z
@JɛﬀE, I'm not sure what you mean. I suggest to solve the problem *directly* using LP. Note that the question asks to find an integral solution if **“capacities, costs, flows, and requirements are non-negative integers”** (this is not *my* assumption). I argue that the LP finds an integral solution since the circulation polytope is integral. However, since this fact is well-known for a more standard version where only edges have capacities, I transform the problem to this form.
Yury
CC BY-SA 3.0
2013-05-18T10:29:32.697Z
Sorry, I misunderstood "duplicate" as the standard trick of replacing an edge with capacity k with k unit-capacity edges. That won't work efficiently if k is exponential in n.  But it isn't necessary to recast the problem as min cost circulation to get an LP; you just have to write it down. Directly.
Jeffε
<max-flow>
Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices
Javad
# Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices

(Asked by: username_0 on 2013-05-17)

Consider the standard minimum-cost flow problem presented [here](http://en.wikipedia.org/wiki/Minimum-cost_flow_problem#Definition). I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and the target $t$) as follows:
$$\sum\limits\_{w \in V } {f({v\_i},w) = \sum\limits\_{w \in V} {f(w,{v\_i}) = } {r\_i}} ,\forall {v\_i} \in V - \{ s,t\},$$
where $r\_i$ is called vertex $v\_i$ flow *requirement* (is there a standard term for it?). Please note that this problem is single-commodity and it is different from the [multi-commodity flow problem](http://en.wikipedia.org/wiki/Multi-commodity_flow_problem).

Moreover, consider that all the capacities, costs, flows, and requirements are non-negative integers. Is there a well-known algorithm to solve this problem in polynomial time? If this is an NP-Complete problem, what's the fastest known algorithm and the approximation method to solve it?

**Tags:** max-flow
> **Comments:**
> **username_0**: I was thinking of duplicating every intermediate node $v_i$ to $v_i^1$ and $v_i^2$ and adding an edge from the former one to the latter one and setting the capacity of the edge as $d_i$ and the cost as a large negative number which is actually a reward for maximizing the flow to the original node. Does this idea work especially because of adding a negative cost?  
> **username_1**: It's possible to solve this problem using Linear Programming. E.g., by duplicating vertices (as in your comment), and connecting t to s, you can restate this problem as a min cost circulation problem, in which the amount of flow on every edge is bounded from above and below. The set of such circulations forms an integral polytope. Thus LP will give you an integral solution.  
> **username_1**: @JɛﬀE, I'm not sure what you mean. I suggest to solve the problem *directly* using LP. Note that the question asks to find an integral solution if **“capacities, costs, flows, and requirements are non-negative integers”** (this is not *my* assumption). I argue that the LP finds an integral solution since the circulation polytope is integral. However, since this fact is well-known for a more standard version where only edges have capacities, I transform the problem to this form.  
> **username_2**: Sorry, I misunderstood "duplicate" as the standard trick of replacing an edge with capacity k with k unit-capacity edges. That won't work efficiently if k is exponential in n.  But it isn't necessary to recast the problem as min cost circulation to get an LP; you just have to write it down. Directly.  

---

## 1 answers

### Answer by username_2 on 2013-05-17. Score: 2

This is a standard variant (if not *the* standard variant) of the minimum-cost flow problem. The "flow requirements" are sometimes called *balance conditions* and sometimes called *vertex supplies/demands*. It can be solved in polynomial time using any number of algorithms.

In particular, you can reduce to the single-source single-target variant in polynomial time as follows:

* Compute a conservative upper bound $M$ on the cost of any flow in your network; for example, let $M = \sum\_e cap(e)\cdot |cost(e)|$. Alternatively, treat $M$ as a symbolic infinite value.
* Add new nodes $s^\*$ and $t^\*$.
* Add arcs $s^\*\to s$ and $t\to t^\*$ with infinite capacity and zero cost.
* For every node $v\_i$ with $r\_i>0$, add an arc $s^\*\to v\_i$ with capacity $r\_i$ and cost $-M$.
* For every node $v\_i$ with $r\_i<0$, add an arc $v\_i\to t^\*$ with capacity $-r\_i$ and cost $-M$.
* Set all vertex requirements to zero.

The minimum-cost feasible flow from $s^\*$ to $t^\*$ in this modified network saturates every arc $s^\*\to v\_i$ and $v\_i\to t^\*$, and the remaining arcs carry the minimum-cost flow from from $s$ to $t$ in the original network that meets all the flow requirements.

> **Comments:**
> **username_0**: I am not sure about the reduction to the original problem. This solution seems to just inject some required flow externally. If $s^*$ and $t^*$ are removed, the saturation effect for every node will be gone and also the flow conservation will not be held any more because an incoming flow of $r_i$ is removed from every node.  

---

