Circulation with Demands

A circulation is a flow with no source or sink — conservation holds everywhere. With lower bounds on edges and demands at vertices, feasibility becomes a genuine question, and one that a plain max-flow solver can answer after a standard transformation.

The problem

Each edge $(u,v)$ has bounds $\ell (u,v)\le f(u,v)\le c(u,v)$. Each vertex has a demand $d(v)$ (positive = must consume, negative = must produce), and conservation reads
${\sum }_{\text{in}}f-{\sum }_{\text{out}}f=d(v).$
Does a feasible $f$ exist?

Transformation 1: eliminate lower bounds

Set $f=\ell +f^{\prime }$ with $0\le f^{\prime }\le c-\ell$. Sending $\ell$ units along every edge unconditionally changes each vertex’s balance, so fold that into the demands:

$d^{\prime }(v)=d(v)+{\sum }_{(u,v)}\ell (u,v)-{\sum }_{(v,w)}\ell (v,w).$

Now every edge has bounds $[0,c-\ell ]$ and the demands have absorbed the mandatory flow.

Transformation 2: demands to a max-flow instance

Add a super-source $S$ and super-sink $T$:

• for each $v$ with $d^{\prime }(v)<0$ (excess supply): edge $S\to v$ with capacity $-d^{\prime }(v)$;
• for each $v$ with $d^{\prime }(v)>0$ (excess demand): edge $v\to T$ with capacity $d^{\prime }(v)$.

A feasible circulation exists iff the max flow from $S$ to $T$ saturates every edge out of $S$ (equivalently, equals ${\sum }_{d^{\prime }(v)>0}{d}^{\prime }(v)$).

The actual circulation is $f=\ell +f^{\prime }$ where $f^{\prime }$ is the flow found.

// after computing d'[] and residual capacities c-l
long long need = 0;
for (int v = 0; v < n; v++) {
    if (dp[v] < 0) { din.addEdge(S, v, -dp[v]); }
    else if (dp[v] > 0) { din.addEdge(v, T, dp[v]); need += dp[v]; }
}
bool feasible = (din.maxflow(S, T) == need);

$s$-$t$ flow with lower bounds

To find an $s$-$t$ flow (not a circulation) respecting lower bounds:

1. Add an edge $t\to s$ with capacity $\infty$ (and lower bound 0) — this converts the flow into a circulation.
2. Run the feasibility test above.
3. For the maximum such flow: after achieving feasibility, delete the $t\to s$ edge and run max flow from $s$ to $t$ on the residual graph, adding to the value already carried.
4. For the minimum such flow: instead run max flow from $t$ to $s$ on the residual and subtract.

Where lower bounds appear

Problem	Lower bound meaning
”Every task must be done at least once”	$\ell =1$ on the task edge
”Each machine runs at least $k$ hours”	$\ell =k$
Chinese postman / route covering every road	$\ell =1$ per road
Matrix rounding (row/column sums preserved)	$\ell =\lfloor x\rfloor$, $c=\lceil x\rceil$
Scheduling with minimum staffing per shift	$\ell$ = required staff
Flow decomposition into exactly $k$ paths	lower bound on the source edge

Matrix rounding is the classic: given a real matrix, round every entry up or down so that all row sums and column sums are also rounded versions of the originals. Model rows as sources, columns as sinks, and each cell as an edge with $\ell =\lfloor a_{ij}\rfloor$, $c=\lceil a_{ij}\rceil$. A feasible circulation is exactly a valid rounding — and one always exists, which is a pleasing constructive proof.

Minimum cost version

Combine with min-cost flow: after the lower-bound transformation, run MCMF instead of max flow. The mandatory $\ell$ flow contributes a fixed $\sum \ell \cdot \text{cost}$ that you add back at the end. Watch for negative costs, which need Bellman-Ford potentials or an initial negative-cycle cancellation.

See also: Maximum Flow · Min-Cost Flow · Eulerian Path