yog/flow/network_simplex

Network Simplex algorithm for minimum cost flow optimization.

Experimental: This module has not been extensively tested against edge cases, large networks, or adversarial inputs. The API and error behavior may change in future releases. Use with caution in production.

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

Example

import yog
import yog/flow/network_simplex

let graph =
  yog.directed()
  |> yog.add_node(1, 10)   // supply 10
  |> yog.add_node(2, 0)    // transshipment
  |> yog.add_node(3, -10)  // demand 10
  |> yog.add_edges([
    #(1, 2, #(5, 2)),   // capacity 5, cost 2
    #(1, 3, #(10, 5)),  // capacity 10, cost 5
    #(2, 3, #(5, 1)),   // capacity 5, cost 1
  ])

let result = network_simplex.min_cost_flow(
  graph,
  get_demand: fn(d) { d },
  get_capacity: fn(e) { e.0 },
  get_cost: fn(e) { e.1 },
)

// result = Ok(MinCostFlowResult(cost: 40, flow: [#(1, 2, 5), #(1, 3, 5), #(2, 3, 5)]))

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

Known Limitations

• List-based internals: The spanning tree uses List for random access, making reads and updates O(n) rather than O(1). Networks with 1000+ nodes/edges may experience significantly reduced performance.
• Cycle timeout: If the algorithm fails to converge within max(500, 5·E) pivots, it returns Error(Timeout).
• No convenience wrappers: Unlike yog/mst, this module does not yet provide pre-baked *_int or *_record variants; you must supply extractor functions.
• Integer only: Costs, capacities, and flows are all Int. Float weights are not supported.
• No Elixir equivalent: yog_ex provides Successive Shortest Path for min-cost flow instead of Network Simplex.

References

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

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

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

pub type NetworkSimplexError {
  Infeasible
  Unbounded
  UnbalancedDemands
  Timeout
}

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)