Yog.Flow.NetworkSimplex (YogEx v0.99.1)

Copy Markdown View Source

Minimum cost flow algorithm using the Network Simplex method.

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 algorithm is a specialized primal simplex method for network flows. In practice, it runs extremely fast (polynomial-like time) and handles arbitrary flows/demands. Unlike pseudo-polynomial algorithms (like Successive Shortest Path), its performance is independent of the total flow capacity (F), making it suitable for large networks.

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
  • Reduced Costs: Modified costs ensuring optimality conditions
  • Spanning Tree: Basis for the simplex method on networks

Implementation Notes

  • Internal state is stored in maps keyed by integer indices (nodes and edges). For very dense graphs, switching to Erlang :array could reduce memory and lookup overhead, but it would be a sizeable refactor.
  • The pivot step uses Enum.find_index/2 to locate the entering and leaving edges inside the fundamental cycle. Each call is O(cycle length); building a position map would speed up hot paths on large instances.
  • The unboundedness test checks whether any original edge flow is at least half of the artificial big-M cost (faux_inf / 2). This 2x buffer is a defensive choice; NetworkX uses flow >= faux_inf directly.
  • Zero-capacity edges are filtered out before solving. Self-loops are kept and treated as non-tree edges, so finite negative-cost self-loops are saturated when beneficial.

Summary

Types

flow_map()

A flow vector assigning an amount of flow to each edge.

min_cost_flow_error()

Errors that can occur during minimum cost flow optimization.

min_cost_flow_result()

Result of a successful minimum cost flow computation.

Functions

min_cost_flow(graph, get_demand, get_capacity, get_cost)

Solves the minimum cost flow problem using the Network Simplex algorithm.

Types

flow_map()

@type flow_map() :: [{Yog.node_id(), Yog.node_id(), integer()}]

A flow vector assigning an amount of flow to each edge.

Each tuple is {from_node, to_node, flow_amount}.

Note: the name flow_map is historical; the type is a list of flow tuples, not a map.

min_cost_flow_error()

@type min_cost_flow_error() ::
  :infeasible | :unbalanced_demands | :unbounded | :timeout

Errors that can occur during minimum cost flow optimization.

  • :infeasible - The demands cannot be satisfied given the edge capacities
  • :unbalanced_demands - The sum of all node demands does not equal 0
  • :unbounded - The network contains a negative-cost cycle with infinite capacity
  • :timeout - The algorithm did not converge within the allowed number of pivots

min_cost_flow_result()

@type min_cost_flow_result() :: %{cost: integer(), flow: flow_map()}

Result of a successful minimum cost flow computation.

Functions

min_cost_flow(graph, get_demand, get_capacity, get_cost)

@spec min_cost_flow(Yog.graph(), (any() -> integer()), (any() -> integer()), (any() ->
                                                                          integer())) ::
  {:ok, min_cost_flow_result()} | {:error, min_cost_flow_error()}

Solves the minimum cost flow problem using the Network Simplex algorithm.

Given a network with edge capacities and costs, and node demands/supplies, finds the flow assignment that satisfies all demands at minimum total cost.

Parameters

  • graph - The flow network (directed graph with edge data representing capacities)
  • get_demand - Function (node_data) -> demand where negative = supply, positive = demand
  • get_capacity - Function (edge_data) -> capacity
  • get_cost - Function (edge_data) -> cost_per_unit

Note: These functions take the node/edge data stored in the graph, not node IDs.

Returns

  • {:ok, result} - Successful computation with %{cost: integer(), flow: flow_map()}
  • {:error, :infeasible} - Demands cannot be satisfied
  • {:error, :unbalanced_demands} - Total supply ≠ total demand
  • {:error, :unbounded} - Negative cycle with infinite capacity found
  • {:error, :timeout} - Maximum pivot limit exceeded

Examples

graph = Yog.directed()
  |> Yog.add_node(1, {-20, nil})
  |> Yog.add_node(2, {10, nil})
  |> Yog.add_node(3, {10, nil})
  |> Yog.add_edges([
    {1, 2, {10, 3}},
    {1, 3, {15, 2}},
    {2, 3, {5, 1}}
  ])

get_demand = fn {d, _} -> d end
get_capacity = fn {c, _} -> c end
get_cost = fn {_, c} -> c end

{:ok, result} = Yog.Flow.NetworkSimplex.min_cost_flow(graph, get_demand, get_capacity, get_cost)