Modeling Capacity-Constrained Flow Networks

From a Physical System to a Directed Network

A network model separates two questions: which movements are permitted, and how much can move along each permitted route. Vertices represent locations or states where flow can enter, leave or be transferred. Directed arcs represent allowed movements. A capacity on an arc gives its maximum permitted flow. The model is useful only when its directions, units and capacity assumptions match the system being described.

For example, a one-way delivery route should be represented by one directed arc, not by an undirected edge. A route available in both directions can be represented by two oppositely directed arcs if the capacity limit applies separately in each direction. If the two directions share one combined capacity, independent arc limits do not express that assumption; the model must include an additional shared constraint or use a different representation.

Capacities and flows must use compatible units. If capacity is measured in packages per hour, every value \(f(a)\) is also a rate in packages per hour. A capacity is an upper bound, not a requirement that the arc carry that amount. Capacity zero means that no positive flow can use the arc. An arc absent from the graph is not an allowed movement at all.

To build a model, first choose the system boundary and identify its source and sink. Then represent the intermediate locations or transfer points by vertices, and add an arc for each permitted direction of movement. Finally, assign each arc a capacity and state what that capacity means. Check that the units agree and that the conservation condition fits the system: it assumes that intermediate vertices do not create, destroy or store flow during the modeled period.

Reading the Definition

The directed graph specifies the network’s structure; the capacity function specifies its limits. If an arc \(uv\) is present, flow may go from \(u\) to \(v\), up to \(c(uv)\). That fact alone says nothing about movement from \(v\) to \(u\): reverse movement requires a separate arc \(vu\). Separate arcs can have different capacities, including capacity zero in one direction.

At a vertex other than \(s\) and \(t\), conservation says that the amount arriving equals the amount departing. It does not say that each incoming arc must be paired with a particular outgoing arc. The flow is an assignment to arcs, constrained by their capacities and by the sum of incoming and outgoing amounts at each intermediate vertex.

The source and sink are designated as the endpoints of the overall transfer. Their net supply and receipt are not needed to define whether an assignment is a flow. In particular, this tutorial does not optimize a flow or compare it with a cut; here the task is to build the network correctly and check assignments against its definition.

Modeling Communication Links

In a communication network, direction is especially important: a link that transmits data from \(x\) to \(y\) need not transmit data in the reverse direction. The capacity might represent the maximum data rate available on that directed link. If the real system has shared bandwidth, a modeling choice is needed to say whether the limit applies per direction or to both directions together.

Modeling Production Through a Transfer Point

A vertex can represent any intermediate stage where material is transferred, not just a geographic location. For instance, an assembly station may receive components from one process and send them to several later processes. If the station can hold inventory during the modeled period, the equality of incoming and outgoing flow may not describe the system; conservation is appropriate when the model treats the station as having no net accumulation during that period.

Two Basic Facts About Feasible Flows

Before analyzing or optimizing flows, it is helpful to know that the definition is consistent and stable under simple operations. These facts also clarify what the constraints permit: zero flow is always an option, and averaging feasible assignments on the same network preserves feasibility.

Proof. Define \(f_0(a)=0\) for every arc \(a\). Since each capacity satisfies \(c(a)\ge0\), we have \(0\le f_0(a)\le c(a)\). At every intermediate vertex, both the incoming and outgoing sums are zero, so they are equal. Thus \(f_0\) is feasible. Now let \(f\) be feasible and \(0\le\theta\le1\). For each arc \(a\), \(f(a)\ge0\) implies \(g(a)=\theta f(a)\ge0\), and \(f(a)\le c(a)\) implies \(g(a)\le f(a)\le c(a)\). At any intermediate vertex, multiplying the equality between the incoming and outgoing sums for \(f\) by \(\theta\) gives the corresponding equality for \(g\). Therefore \(g\) is feasible. \(\square\)

Proof. Fix any arc \(a\). Both flows are nonnegative, so \(h(a)\ge0\). Since \(f_1(a)\le c(a)\), \(f_2(a)\le c(a)\), and both coefficients are nonnegative, we have \(h(a)\le\theta c(a)+(1-\theta)c(a)=c(a)\). Now fix an intermediate vertex \(v\). For each of \(f_1\) and \(f_2\), the incoming sum equals the outgoing sum at \(v\). Multiplying the first equality by \(\theta\), the second by \(1-\theta\), and adding them shows that the incoming sum for \(h\) equals its outgoing sum. Thus \(h\) satisfies every capacity and conservation condition and is feasible. \(\square\)

The theorem is useful when quantities are divisible or represent average rates: mixing two feasible operating patterns does not violate any capacity or conservation equation. It relies on using the same network and capacity function for both flows. It does not say that adding two feasible flows always gives another feasible flow, because their combined use of an arc could exceed its capacity.

Common Modeling Mistake: A Shared Two-Way Capacity

Suppose a road permits travel in both directions and can carry at most \(10\) vehicles per hour in total. A tempting model adds arcs \(u\to v\) and \(v\to u\), each with capacity \(10\), and assigns \(8\) vehicles per hour to each direction. The individual checks \(8\le10\) pass, but the road would carry \(8+8=16\) vehicles per hour, exceeding its shared limit of \(10\).

The correction is to state what “capacity \(10\)” means before choosing the arcs. If the road has capacity \(10\) in each direction independently, the two arcs each having capacity \(10\) is appropriate. If \(10\) is a combined two-way limit, the two independent arc bounds do not encode the real restriction; the model needs the additional condition \(f(uv)+f(vu)\le10\), or a representation that enforces that shared resource limit.

More generally, an arc capacity constrains one directed movement. It does not automatically constrain a collection of arcs that share a physical resource. A good model records both the physical interpretation of every capacity and the mathematical constraint that represents it.