Does the method maximize the delivered quantity?

Its stated task is to satisfy specified demands at minimum cost. Maximum-flow questions are different formulations.

Can a balanced model still be infeasible?

Yes. The network may lack enough capacity to connect supplies to demands.

Are all library sign conventions identical?

No. Check whether a positive node value means supply or demand before transferring a model between tools.

AI Glossary / Graphs and symbolic AI / Intermediate

Capacity Scaling Minimum Cost Flow

Definition

Capacity Scaling Minimum Cost Flow is a network-flow method that finds the least-cost way to satisfy specified supplies and demands while respecting edge capacities. Capacity scaling organizes the computation into phases that handle larger flow amounts before refining smaller ones. In this glossary's NetworkX context, capacity_scaling implements a successive shortest augmenting path approach with this scaling strategy.

What it means

A minimum-cost flow model includes locations or states, allowed directed transfers, transfer capacities, and a cost per unit on each transfer. Some nodes supply flow, some require it, and others pass it onward. The goal is to meet the required balances at minimum total cost.
This differs from merely sending as much flow as possible. Demand specifies how much must be delivered, while cost determines which feasible routing is preferred. Scaling changes how the algorithm solves the model; it does not mean scaling up the real network, increasing its capacities, or approximating away small customer demands.

How it works

The algorithm works with residual capacity, which describes remaining transfer options and the ability to revise earlier flow assignments. In broad terms, a scaling threshold restricts attention to sufficiently large residual movements during a phase. Cost-aware augmenting paths move flow between nodes with excess and deficit, and finer thresholds progressively handle smaller adjustments.
The full method also maintains the cost information needed to choose and justify augmentations. A simple instruction to choose the cheapest original edge repeatedly is not equivalent, because shared capacities and later revisions matter. Once the required balances are satisfied and optimality conditions hold, the result includes a flow allocation and its total modeled cost.

Three practical examples

A distribution model allocates stock from warehouses to stores using routes with per-unit costs and shipment limits.
A task-allocation model represents permissible assignments as capacity-limited edges with assignment costs.
A time-expanded planning graph represents movement or inventory across periods, provided the modeled quantities and costs fit a minimum-cost flow formulation.

Think of it this way

Think of planning a delivery using broad allocation adjustments first and finer corrections afterward. This helps explain the idea of scaling. The analogy is limited because the algorithm's phases are mathematical operations on a residual network, not a requirement to dispatch large real shipments before small ones. Its computed final plan, rather than the internal augmentation order, is what an application normally uses.

Worked example

Suppose warehouse W supplies 7 units to store T. Route W-A-T has capacity 4 on each edge, with per-unit costs 2 and 1, giving route cost 3. Route W-B-T has capacity 5 on each edge, with costs 4 and 1, giving route cost 5. There are no other edges.
Let x units use the cheaper route. Then 7 minus x use the second route. Capacities require x at most 4 and 7 minus x at most 5, so feasible x lies from 2 through 4. Total cost is 3x + 5(7 minus x), or 35 minus 2x. This decreases as x increases, so x = 4 is optimal and the remaining 3 units use B. Total cost is 12 + 15 = 27. Under NetworkX's convention, W has demand -7, T has demand +7, and A and B have zero demand. This calculation verifies the final solution, not the algorithm's internal phase sequence.

Illustrative case study

At fictional Alder Supply, a planning team builds a small distribution graph and checks that every store's demand can be met. It first verifies the flow balances and route capacities, then compares total cost with a manually solved small example before using larger models.
When the software reports infeasibility, the team checks both genuine shortages and data mistakes such as reversed demand signs. This fictional case illustrates validation of a flow model and its result; it does not claim cost savings or imply that a mathematically feasible routing captures every operational restriction.

Common misconceptions and mistakes

Balanced total supply and demand is necessary but not sufficient for feasibility: capacities or missing routes may prevent delivery. Minimum-cost flow also assumes a specified cost structure. Fixed dispatch charges, nonlinear discounts, or indivisible multi-item requirements may need a different or extended model.
Capacity scaling is different from cost scaling, another optimization technique. Implementation conventions matter too: NetworkX uses negative demand for supply, while other libraries may use the opposite sign. Its documented routine does not support floating-point edge weights. Representing costs in integer minor units can be appropriate when done consistently and without changing the intended precision.

Business use

Businesses can use this method where logistics or allocation decisions have a natural network structure. A review should check node balances, units, edge capacities, cost units, and the meaning of any missing attributes. NetworkX treats a missing capacity as unbounded and a missing edge cost as zero, so omissions can materially alter a model. Keep solver errors, infeasibility, and an unbounded objective distinct; each calls for a different investigation.

Check your understanding

In the worked example, why not send all 7 units along the route costing 3 per unit?

Answer: Its capacity is only 4. The remaining 3 units must use the other available route to meet demand.

Related terms

Network Simplex
minimum-cost flow
capacity constraint
residual network
augmenting path
supply and demand
cost scaling

Learn next

Reduce the second route's capacity to 2 and check feasibility before calculating cost. Then increase the cheaper route's cost and solve the small model again. This separates capacity-driven feasibility from cost-driven preference and makes model validation easier.

Model validation

Sources

Sources: NetworkX, official capacity_scaling documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.capacity_scaling.html . JGraphT, official capacity-scaling minimum-cost-flow implementation explanation: https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/mincost/CapacityScalingMinimumCostFlow.html .

Previous: Capability study Next: Capsule neural network