Minimum-cost flow problem

A network optimization problem that routes specified supplies and demands through a capacitated network while minimizing the total cost of flow.

Flow conservation: A constraint requiring inflow and outflow at each network node to balance with its supply or demand. It expresses the balance equations that every feasible flow must satisfy.
Directed graph: A set of vertices connected by edges that each have a specified direction. Flow paths follow directed arcs from supply nodes toward demand nodes.
Transportation problem: A linear optimization problem that ships goods from suppliers to destinations at minimum total cost. It is a special case with direct supplier-to-destination shipping arcs.
Maximum flow problem: A network optimization problem that maximizes the amount sent from a source to a sink under capacity limits. It maximizes throughput, whereas minimum-cost flow minimizes expense for specified balances.
Network simplex algorithm: A simplex method specialized for linear optimization problems whose constraint matrices describe networks. It exploits network structure to optimize flows through successive tree-basis changes.
Capacity constraint: A bound restricting a variable or resource to a permitted range. Each arc’s upper bound limits how much flow it can carry.
Assignment problem: A combinatorial optimization problem matching agents to tasks at minimum total assignment cost. Unit supplies, unit demands, and assignment arcs yield this familiar special case.
Minimum-cost maximum-flow problem: A network problem that sends the greatest possible source-to-sink flow and minimizes its cost. It combines a throughput objective with cost minimization instead of fixing supplies in advance.
Successive shortest path algorithm: An algorithm that repeatedly sends flow along a cheapest available path between supply and demand nodes. It builds an optimal flow by augmenting along shortest residual paths.
Supply and demand: Quantities available at source nodes and required at sink nodes in a network. Node balances specify where flow originates and where it must arrive.

Linked from 8 pages