yog/flow/network_simplex

Network Simplex algorithm for minimum cost flow optimization.

This module solves the minimum cost flow problem: find the cheapest way to send a given amount of flow through a network where edges have both capacities and costs per unit of flow.

Algorithm

The Network Simplex is a specialized version of the simplex algorithm for network flow problems. It maintains a spanning tree of basic edges and iteratively pivots to improve the solution, similar to how the transportation simplex works for assignment problems.

Key Concepts

• Minimum Cost Flow: Route flow to satisfy demands at minimum total cost
• Node Demands: Supply nodes (negative demand) and demand nodes (positive demand)
• Edge Costs: Price per unit of flow on each edge
• Potentials (π): Dual variables for reduced cost computation
• Reduced Costs: Modified costs ensuring optimality conditions
• Spanning Tree: Basis for the simplex method on networks

Problem Formulation

Given:

• Graph G = (V, E) with capacities u(e) and costs c(e)
• Node demands b(v) where Σb(v) = 0 (conservation)

Find flow f(e) that:

• Minimizes: Σ c(e) × f(e) (total cost)
• Subject to: 0 ≤ f(e) ≤ u(e) (capacity constraints)
• And: flow conservation at each node

Use Cases

• Transportation planning: Minimize shipping costs with vehicle capacities
• Supply chain: Optimize distribution from warehouses to retailers
• Telecommunications: Route calls at minimum cost with link capacities
• Workforce scheduling: Assign workers to shifts minimizing total cost
• Circulation problems: Fleet management and inventory routing

Performance Notes

This implementation uses list-based data structures for the internal spanning tree representation. While algorithmically correct, random access and updates are O(n) rather than O(1). For large flow networks (1000+ nodes/edges), this may impact performance. Consider using alternative approaches for very large-scale problems:

• Erlang FFI to :digraph or optimized C libraries
• Specialized MCF solvers for production-scale optimization

References

• Wikipedia: Minimum-Cost Flow Problem
• Wikipedia: Network Simplex Algorithm
• Network Flows - Ahuja, Magnanti, Orlin
• CP-Algorithms: Min-Cost Flow

pub type EnteringEdge =
  #(Int, Int, Int, Int)

pub type FlowMap =
  List(#(Int, Int, Int))

pub type MinCostFlowResult {
  MinCostFlowResult(cost: Int, flow: List(#(Int, Int, Int)))
}

pub type NetworkSimplexError {
  Infeasible
  Unbounded
  UnbalancedDemands
}

pub fn min_cost_flow(
  graph: model.Graph(n, e),
  get_demand: fn(n) -> Int,
  get_capacity: fn(e) -> Int,
  get_cost: fn(e) -> Int,
) -> Result(MinCostFlowResult, NetworkSimplexError)