Minimum-cost flow is an optimization problem that finds the cheapest way to send a specific amount of "flow" (material, data, or goods) from source nodes to sink nodes through a network. It minimizes total transportation costs, ensuring flow does not exceed edge capacities.
Key Aspects of Min-Cost Flow:
- Capacity Constraints: Every edge has a maximum capacity that cannot be exceeded.
- Cost per Unit: Each unit of flow on an edge has a associated cost.
- Flow Conservation: For every node, flow in must equal flow out, except for supply nodes () and demand nodes ().
- Goal: Minimize(total cost) while satisfying all supply/demand needs.
Common Applications:
- Logistics & Supply Chain: Shipping goods from factories to consumers at minimum cost.
- Telecommunications: Routing data packets to reduce latency and maximize bandwidth utilization.
- Energy Distribution: Transporting electricity or liquids through pipelines.
- Assignment Problems: Matching tasks to workers efficiently.
Solving Techniques:
The problem is typically solved using variations of the Successive Shortest Path algorithm, which uses Bellman-Ford or Dijkstra's algorithm with potentials to find the cheapest path, often using solvers such as Gurobi or Google OR-Tools.
The problem is typically solved using variations of the Successive Shortest Path algorithm, which uses Bellman-Ford or Dijkstra's algorithm with potentials to find the cheapest path, often using solvers such as Gurobi or Google OR-Tools.
