Does the network have to describe physical transport?

No. Many assignment and allocation problems can be represented as network flows.

Is a zero total demand enough to guarantee a solution?

No. The available routes and capacities must also support the required balances.

Does “weight” mean route capacity?

In the cited NetworkX function, weight is unit cost, while capacity is a separate attribute.

AI Glossary / Graphs and symbolic AI / Advanced

Network Simplex

Definition

Network simplex is an optimization algorithm for finding a minimum-cost flow through a network while satisfying supply, demand, and capacity constraints. It adapts the simplex approach to the special structure of network-flow problems, using a tree-based representation and flow adjustments that preserve node balances.

What it means

Imagine goods moving from suppliers through a distribution network to customers. Each route has a maximum capacity and a cost per unit. The objective is to meet the specified requirements at the lowest total route cost, rather than merely send as much flow as possible.

The same mathematical model can represent assignments, transfers, or other divisible quantities. Network simplex is an algorithm for solving that model; it is not a prediction model or a neural network. The word network refers to a directed graph of nodes and arcs with defined flow relationships.

How it works

The model minimizes the sum of each arc's flow multiplied by its unit cost. Every node must satisfy a balance equation, and each arc's flow must respect its bounds. A supply node sends more than it receives, a demand node receives more than it sends, and a transshipment node balances incoming and outgoing flow.

Network simplex represents a basis using a spanning-tree structure, with other arcs held at bounds. A pivot introduces an eligible arc, creating a cycle through which flow can be adjusted. A limiting arc leaves the basis, and the tree and associated information are updated. Degenerate pivots may change the basis without immediately lowering cost, so implementation rules matter.

In NetworkX's convention, negative node demand means supply and positive demand means consumption. Total demand must sum to zero, but balance alone does not guarantee feasible routes. The implementation returns a minimum cost and a flow dictionary or reports relevant failure conditions.

Three practical examples

Distribution planning: allocate shipments across routes with different capacities and per-unit transport costs.
Resource assignment: represent eligible assignments as arcs and choose a cost-minimizing feasible allocation.
Transshipment design: route required quantities through intermediate hubs while preserving flow balance at each hub.

Think of it this way

Think of redistributing water through a pipe network so that every tank receives its required amount while pumping cost falls. Adjustments must respect pipe capacities and preserve the required balances.

The analogy assumes a linear flow model. Real water pressure, nonlinear pumping costs, delivery time windows, and indivisible operational decisions may require additional models rather than a direct network-simplex formulation.

Worked example

Supplier S must deliver six units to destination T. There are two routes. Route S→A→T has capacities four on both arcs and costs two and one per unit. Route S→B→T has capacities six on both arcs and costs one and four per unit. Thus, the routes cost three and five per delivered unit.

Send four units through A and two through B. The total cost is 4×(2+1)+2×(1+4)=12+10=22. At S, total outflow is six; at T, total inflow is six. A receives and sends four, while B receives and sends two. Every capacity is respected.

To check optimality directly, let x be the quantity sent through A. Feasibility requires 0≤x≤4, with 6−x through B. Total cost is 3x+5(6−x)=30−2x, minimized at the largest feasible x, namely four. The cost is therefore 22.

If the cheaper route's capacity rose to five, the optimum would send five through A and one through B, costing 20. If demand instead rose to eleven with the original capacities, the model would be infeasible because the two routes together carry at most ten. These are hand-checked model calculations, not a recorded solver run or a network-simplex pivot trace.

Illustrative case study

Fictional case: a parts distributor models transfers between depots and service centers. Its first optimization result appears unusually cheap because a missing cost attribute is interpreted as zero on one route.

The team introduces input checks for explicit costs, capacities, and node balances, then compares the returned flow with a small manually solved case. It keeps handling constraints outside the basic model visible for operational review. The fictional case illustrates the importance of model data, not a measured saving.

Common misconceptions and mistakes

Network simplex does not solve every logistics problem unchanged. Fixed vehicle charges, incompatible products, and time-dependent constraints may break the simple linear flow structure. A low-cost flow can still be unsuitable if necessary constraints were omitted.

Do not confuse minimum-cost flow with maximum flow. One satisfies stated balances cheaply; the other maximizes a transported quantity under its own formulation. A combined objective needs an appropriate model or procedure.

Also, equal total supply and demand is necessary but not sufficient for feasibility. Disconnected routes or bottlenecks can prevent delivery. An unbounded cost objective is another distinct condition, possible with unlimited negative-cost circulation in an unsuitable model.

Business use

The algorithm supports decisions where quantities, route capacities, and linear costs can be specified clearly. Validate units: a demand in pallets cannot be mixed with capacities in individual items without conversion.

For the cited NetworkX implementation, the documentation warns about floating-point weights or demands. Integer scaling may help when it represents the intended precision, but teams should document the scaling and rounding choices. Verify balances, capacities, and recomputed cost before interpreting a returned plan operationally.

Check your understanding

A cheap route carries at most three units at cost two each, and an unlimited alternative costs five each. What is the minimum cost of delivering four units?

Answer: Three units use the cheap route and one the alternative, costing 3×2+5=11.

Related terms

Linear programming
Spanning Trees
minimum-cost flow
simplex method
spanning tree
capacity
flow conservation
reduced cost
transportation problem

Learn next

formulate node balance equations for a small delivery graph, then compare maximum flow with minimum-cost flow. Study reduced costs and tree pivots after the model itself is clear.

Maximum Flow

Sources

NetworkX documents its primal network-simplex implementation, conventions, and numerical limitations: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.network_simplex.html

The implementation exposes its tree structure and pivot operations: https://networkx.org/documentation/stable/_modules/networkx/algorithms/flow/networksimplex.html

The delivery example and fictional distributor are original illustrations.

Previous: Network sampling Next: Network throughput