Circulation problem¶

A network-flow feasibility or optimization problem assigning edge flows within lower and upper bounds while conserving flow at every vertex.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3688
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomain: Combinatorial Optimization → Operations Research

Core Idea¶

Unlike ordinary source-sink flow every vertex obeys balance unless supplies and demands are explicitly added, lower bounds require a feasibility transformation and multicommodity circulation is a harder variant. Lower bounds are subtracted from capacities, their induced node imbalances are connected to a super-source and super-sink and a max-flow test determines whether residual capacity can restore conservation; costs can then optimize feasible circulation. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

The Balanced Pipes Puzzle

Picture water pipes joined together in a loop, with no tap and no drain. At every joint, the same amount of water has to come in as goes out. Each pipe has to carry at least a little and no more than it can hold. The circulation problem asks: can you make the water flow so every rule is followed?

The In-Equals-Out Network

Imagine a network of one-way roads with trucks driving on them. Each road has a limit on how many trucks it can carry, and some roads also need at least a certain number of trucks. At every crossing, the same number of trucks must come in as go out. A circulation problem asks: can you choose how many trucks go on each road so that every rule is followed? Unlike some flow puzzles, there's no special starting place or ending place; the flow just goes around. Sometimes each road also has a cost, and you look for the cheapest flow that works.

Bounded Network Circulation

In a circulation problem you have a directed graph (points connected by one-way edges). Each edge has a lower bound and an upper bound on how much can flow along it. Unlike an ordinary flow problem with one source and one sink, here every vertex must balance: inflow equals outflow, unless you explicitly add supplies or demands at some vertices. The question is whether a flow meeting all the bounds and balance rules, called a feasible circulation, exists. The standard trick: subtract the lower bounds first, which leaves some vertices with extra or missing flow; attach those to a new 'super-source' and 'super-sink,' and run a maximum-flow algorithm. If the max flow fills all those new edges, a feasible circulation exists. You can also add costs and look for the cheapest circulation, and there's a harder version with several different kinds of flow sharing the edges.

In the circulation problem, a directed graph has on each edge a flow variable constrained between a lower bound and an upper capacity, and flow conservation must hold at every vertex; unlike ordinary source-sink flow, there are no exempt vertices unless supplies and demands are explicitly added. The central question is feasibility. Lower bounds are handled by a transformation: subtract each edge's lower bound from its capacity, compute the resulting net imbalance at each vertex, connect vertices with surplus to a super-source and those with deficit to a super-sink, and run max-flow. A feasible circulation exists exactly when this max-flow saturates all the super-source edges, and the residual network yields the certificate. With edge costs, one can then optimize over feasible circulations, giving the minimum-cost circulation problem. The multicommodity variant, where several distinct commodities share capacities, is harder. Correct statements make explicit the graph, bounds, conservation, any supplies, demands and costs, and which variant is meant.

Scope of Application¶

Circulation problem belongs to combinatorial optimization and is useful where the analyst can specify the typed combinatorial optimization carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the directed graph with vertices and edges, lower and upper capacity bounds, flow variable on each edge, node conservation at every vertex, optional supplies demands and edge costs, feasibility, lower-bound reduction and super-source or super-sink construction, residual network, feasible-circulation certificate and minimum-cost and multicommodity variants are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the directed graph with vertices and edges, lower and upper capacity bounds, flow variable on each edge, node conservation at every vertex, optional supplies demands and edge costs, feasibility, lower-bound reduction and super-source or super-sink construction, residual network, feasible-circulation certificate and minimum-cost and multicommodity variants are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Circulation problem. Circulation problem compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed combinatorial optimization carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the directed graph with vertices and edges, lower and upper capacity bounds, flow variable on each edge, node conservation at every vertex, optional supplies demands and edge costs, feasibility, lower-bound reduction and super-source or super-sink construction, residual network, feasible-circulation certificate and minimum-cost and multicommodity variants are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of combinatorial optimization because they reuse the typed combinatorial optimization carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, Lower bounds are subtracted from capacities, their induced node imbalances are connected to a super-source and super-sink and a max-flow test determines whether residual capacity can restore conservation; costs can then optimize feasible circulation., and type the carrier, state every parameter and convention in the definition, test that the directed graph with vertices and edges, lower and upper capacity bounds, flow variable on each edge, node conservation at every vertex, optional supplies demands and edge costs, feasibility, lower-bound reduction and super-source or super-sink construction, residual network, feasible-circulation certificate and minimum-cost and multicommodity variants are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Circulation problem Domain-specific

Parents (1) — outgoing typed relations

Circulation problem is a kind of Coordination Prime

It remains its own entry because its identity is fixed by the directed graph with vertices and edges, lower and upper capacity bounds, flow variable on each edge, node conservation at every vertex, optional supplies demands and edge costs, feasibility, lower-bound reduction and super-source or super-sink construction, residual network, feasible-circulation certificate and minimum-cost and multicommodity variants.

Hierarchy paths (5) — routes to 4 parentless roots

Circulation problem → is a kind of Coordination → presupposes Concurrency

Show alternative paths (4)

Neighborhood in Abstraction Space¶

Circulation problem sits in a crowded region of the domain-specific corpus (15^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization on Graphs (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25