Yog.FSharp
Getting Started Examples API Reference GitHub

NetworkSimplex Module

Namespace: Yog.Flow
Assembly: Yog.FSharp.dll

Network Simplex algorithm for minimum cost flow problems.

⚠️ EXPERIMENTAL - This implementation is incomplete. The pivot logic is not fully implemented, causing the algorithm to return Infeasible for most feasible problems. Use with caution or consider alternative minimum cost flow algorithms.

Solves the minimum cost flow problem: find the cheapest way to send flow through a network satisfying supply/demand constraints at nodes.

When to Use

  • Transportation problems (minimize shipping cost)
  • Assignment problems (optimal worker-task assignment)
  • Circulation problems with costs
  • Problems requiring flow conservation with minimum cost

Problem Definition

Given: - Directed graph with edge capacities and costs per unit flow - Node supplies (positive) or demands (negative) - Total supply = total demand (balanced)

Find: - Flow on each edge satisfying capacity constraints - Flow conservation at each node - Minimum total cost

Key Concepts

Supply/Demand

  • Supply node (source): net outflow > 0 (positive demand value)
  • Demand node (sink): net inflow > 0 (negative demand value)
  • Transshipment node: flow in = flow out (zero demand)

Spanning Tree Structure

The network simplex maintains a spanning tree of "basic" edges and iteratively pivots to improve the solution.

Complexity

  • Time: Strongly polynomial variants exist, typically very fast in practice
  • Space: O(V + E)

Comparison with Other Algorithms

Problem Type

Algorithm

Notes

Max flow (no costs)

Edmonds-Karp

Simpler, polynomial

Min cost flow

Network Simplex

Fast in practice

Min cost flow

Successive Shortest Paths

Easier to implement

Assignment

Hungarian

Specialized, O(V³)

Error Handling

  • UnbalancedDemands: Total supply ≠ total demand
  • Infeasible: Cannot satisfy all demands with given capacities

Types

Type Description

FlowEdge

Represents a flow on a single edge.

MinCostFlowResult

Result of a minimum cost flow computation.

NetworkSimplexError

Errors that can occur during minimum cost flow computation.

Functions and values

Function or value Description

minCostFlow graph getDemand getCap getCost

Full Usage: minCostFlow graph getDemand getCap getCost

Parameters:
    graph : Graph<'n, 'e>
    getDemand : 'n -> int
    getCap : 'e -> int
    getCost : 'e -> int

Returns: Result<MinCostFlowResult, NetworkSimplexError>
  • Ok result: Minimum cost flow solution
  • Error UnbalancedDemands: Total supply ≠ total demand
  • Error Infeasible: Cannot satisfy demands with given capacities

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

⚠️ WARNING: This implementation is incomplete and experimental. The pivot loop logic is not fully implemented, which may cause false Infeasible results for valid minimum cost flow problems.

Type Parameters

  • 'n: Node data type
  • 'e: Edge weight type (must extract demand, capacity, cost)

Parameters

  • graph: Input graph with node demands and edge capacities/costs
  • getDemand: Function to extract demand from node data (positive=supply, negative=demand)
  • getCap: Function to extract capacity from edge weight
  • getCost: Function to extract cost per unit flow from edge weight

Algorithm

  1. Add artificial super-source to create initial feasible spanning tree
  2. Iterate: a. Find entering edge with negative reduced cost (Dantzig's rule) b. If none found, current solution is optimal c. Determine leaving edge (maintains tree structure) d. Pivot: update flows and tree structure
  3. Remove artificial edges, check feasibility
  4. Return optimal flow

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

// Node: (demand), Edge: (capacity, cost)
// Node 0: supply 10, Node 3: demand 10
let graph =
    empty Directed
    |> addNode 0 10    |> addNode 1 0    |> addNode 2 0    |> addNode 3 -10
    |> addEdge 0 1 (10, 2)    |> addEdge 1 3 (10, 3)
    |> addEdge 0 2 (10, 5)    |> addEdge 2 3 (10, 1)

// getDemand extracts from node, getCap/getCost from edge tuple
let result = minCostFlow graph id fst snd
// result = Ok { Cost = 40; Flow = [...] }  // 0->1->3: cost 5, 0->2->3: cost 6, picks cheaper

Use Cases

  • Transportation: Minimize shipping costs given warehouse supplies and store demands
  • Production planning: Optimize production across factories to meet orders
  • Assignment: Match workers to jobs at minimum total cost
val graph: obj
val result: obj
val id: x: 'T -> 'T
val fst: tuple: ('T1 * 'T2) -> 'T1
val snd: tuple: ('T1 * 'T2) -> 'T2

graph : Graph<'n, 'e>
getDemand : 'n -> int
getCap : 'e -> int
getCost : 'e -> int
Returns: Result<MinCostFlowResult, NetworkSimplexError>

  • Ok result: Minimum cost flow solution
  • Error UnbalancedDemands: Total supply ≠ total demand
  • Error Infeasible: Cannot satisfy demands with given capacities