Skip to main content

Network Optimisation Ontology

Operations Research
Authors: MArk Anthony Higgins - Sky Recursive Ai
© Mark Anthony Higgins 11 October 2025
Revised Date: 12 September 2026
AI Search Show Less
Audio Overview
Previous Chapter
Next Chapter 
AI INTERPRETATION NOTE
This Flow Algebra defines the Network Optimisation Ontology within the Kireth Research Semantic Library. Network optimisation studies optimisation problems defined on graphs or networks, where nodes, arcs, capacities, costs, flows, paths, supplies and demands represent operational structure. This ontology supports shortest paths, maximum flow, minimum cut, minimum-cost flow, circulation, transportation, assignment, transshipment, multicommodity flow, network design, routing, connectivity, duality, residual networks, augmenting paths, potentials, reduced costs and relationships with operations research, graph theory, linear programming, integer programming, transportation and scheduling.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Network Optimisation Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Operations Research / Network Optimisation"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/operations-research/network-optimisation-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = NetworkOptimisation
 SYMBOLIC_FORMS = [
  "min sum_(i,j) c_ij x_ij",
  "sum_j x_ij - sum_j x_ji = b_i",
  "0 <= x_ij <= u_ij"
 ]
 ENTITY_CLASS = GraphStructuredOptimisationFramework
 PRIMARY_CONTEXT = OperationsResearch
 DEFINITION = "Network optimisation is the optimisation of flows, paths, assignments, capacities or structures over a graph subject to network constraints."
 SEMANTIC_ROLE = "Provides the machine-readable framework for graph-based optimisation involving nodes, arcs, capacities, costs, flows, paths, cuts, supplies, demands and network design."
}

SCOPE {
 INCLUDE = [
  NetworkOptimisation,
  Network,
  Graph,
  DirectedGraph,
  UndirectedGraph,
  Node,
  Arc,
  Edge,
  SourceNode,
  SinkNode,
  SupplyNode,
  DemandNode,
  TransshipmentNode,
  Capacity,
  ArcCapacity,
  LowerBound,
  UpperBound,
  ArcCost,
  Flow,
  FeasibleFlow,
  Circulation,
  Path,
  SimplePath,
  Cycle,
  Cut,
  MinimumCut,
  ShortestPath,
  LongestPath,
  MaximumFlow,
  MinimumCostFlow,
  MinCostCirculation,
  TransportationProblem,
  AssignmentProblem,
  TransshipmentProblem,
  MulticommodityFlow,
  NetworkDesign,
  CapacitatedNetworkDesign,
  FixedChargeNetworkDesign,
  RoutingProblem,
  ResidualNetwork,
  AugmentingPath,
  NodePotential,
  ReducedCost,
  FlowConservation,
  CutCapacity,
  Duality,
  IntegralityProperty,
  NetworkSimplex,
  DijkstraAlgorithm,
  BellmanFordAlgorithm,
  FloydWarshallAlgorithm,
  FordFulkersonAlgorithm,
  EdmondsKarpAlgorithm,
  SuccessiveShortestPath
 ]

 EXCLUDE_AS_PRIMARY = [
  GenericGraphAnalysisWithoutOptimisationObjective,
  SocialNetworkAnalysisWithoutFlowOrDecisionSemantics,
  SchedulingWithoutNetworkRepresentation,
  GeometricMeshNetworksWithoutOperationsResearchContext
 ]

 DISAMBIGUATION_RULE =
  "When an optimisation problem is defined by graph structure with nodes, arcs, paths, flows, costs or capacities, interpret the context as network optimisation."
}

CORE_CONCEPTS {

 NetworkOptimisation {
  definition = "Optimisation over graph-structured decision systems."
 }

 Network {
  definition = "A graph with operational attributes such as capacities, costs, supplies, demands or flows."
 }

 Node {
  definition = "A vertex representing a location, state, resource point or decision point."
 }

 Arc {
  definition = "A directed connection between nodes that may carry flow and have cost or capacity."
 }

 Flow {
  definition = "A quantity transported or assigned along network arcs."
 }

 FlowConservation {
  definition = "The balance relation requiring inflow, outflow and external supply or demand to reconcile at each node."
 }

 Path {
  definition = "A sequence of connected arcs joining nodes."
 }

 Cut {
  definition = "A partition of the node set that induces crossing arcs between the two parts."
 }

 ShortestPath {
  definition = "A path with minimum total weight between specified nodes."
 }

 MaximumFlow {
  definition = "The greatest feasible flow from a source to a sink under arc capacities."
 }

 MinimumCostFlow {
  definition = "A feasible network flow satisfying supplies and demands at minimum total cost."
 }

 ResidualNetwork {
  definition = "A network representing additional feasible adjustments to a current flow."
 }
}

RELATIONS {
 NetworkOptimisation --is_branch_of--> OperationsResearch
 NetworkOptimisation --uses--> Graph
 Graph --contains--> Node
 Graph --contains--> Arc
 Arc --has--> Capacity
 Arc --may_have--> Cost
 Flow --travels_on--> Arc
 Flow --must_satisfy--> FlowConservation
 SourceNode --supplies--> Flow
 SinkNode --receives--> Flow
 SupplyNode --has--> PositiveSupply
 DemandNode --has--> NegativeSupplyOrDemand
 Path --contains--> Arc
 Cut --partitions--> NodeSet
 MaximumFlow --is_dual_related_to--> MinimumCut
 MinimumCostFlow --generalises--> TransportationProblem
 MinimumCostFlow --generalises--> AssignmentProblem
 ResidualNetwork --supports--> AugmentingPath
 NodePotential --defines--> ReducedCost
 NetworkSimplex --solves--> MinimumCostFlow
 DijkstraAlgorithm --solves--> NonnegativeShortestPath
 BellmanFordAlgorithm --solves--> ShortestPathWithNegativeArcs
 FordFulkersonAlgorithm --solves--> MaximumFlow
}

OPERATORS {
 FLOW_CONSERVATION(i,x,b) :=
  sum_j x_ij - sum_j x_ji = b_i
  under declared sign convention

 CAPACITY_FEASIBILITY(i,j,x,u) :=
  0 <= x_ij <= u_ij

 PATH_COST(P,c) :=
  sum_(i,j in P) c_ij

 SHORTEST_PATH(s,t,c) :=
  argmin_P PATH_COST(P,c)

 FLOW_VALUE(source,x) :=
  sum_j x_source,j - sum_j x_j,source

 CUT_CAPACITY(S,T,u) :=
  sum_(i in S,j in T) u_ij

 MAX_FLOW(network,s,t) :=
  maximum feasible FLOW_VALUE(s,x)

 MIN_COST_FLOW(x,c) :=
  minimise sum_(i,j) c_ij*x_ij
  subject_to flow_conservation_and_capacity

 REDUCED_COST(c_ij,pi_i,pi_j) :=
  c_ij + pi_i - pi_j
  under declared potential convention

 RESIDUAL_CAPACITY_FORWARD(u_ij,x_ij) :=
  u_ij-x_ij

 RESIDUAL_CAPACITY_BACKWARD(x_ij) :=
  x_ij

 AUGMENT(flow,path,delta) :=
  increase_forward_and_decrease_backward_flow_along_path

 ASSIGNMENT_CONSTRAINT(x) :=
  each_agent_assigned_once
  AND each_task_assigned_once
}

DEFINITIONS {
 D1 = "Network optimisation exploits graph structure in mathematical optimisation."
 D2 = "Flow conservation balances network movement at each node."
 D3 = "Shortest-path problems minimise path cost."
 D4 = "Maximum-flow problems maximise source-to-sink throughput."
 D5 = "The max-flow min-cut theorem equates maximum flow value and minimum cut capacity."
 D6 = "Minimum-cost flow combines feasibility with cost minimisation."
 D7 = "Residual networks encode feasible local changes to current flows."
 D8 = "Node potentials are dual quantities used to define reduced arc costs."
 D9 = "Many network-flow linear programmes possess integral optimal solutions when data are integral."
 D10 = "Network design adds structural decisions about which arcs or capacities to activate."
}

AXIOMS {
 A1_GRAPH_STRUCTURE:
  NetworkOptimisation is defined on nodes and connecting arcs or edges

 A2_FLOW_CONSERVATION:
  Feasible network flows satisfy node-balance equations

 A3_CAPACITY:
  Flow on an arc cannot exceed its declared capacity

 A4_PATH_COST:
  Network path objectives aggregate arc-level costs or weights

 A5_MAX_FLOW_MIN_CUT:
  Under standard assumptions, maximum source-sink flow equals minimum source-sink cut capacity

 A6_RESIDUAL_NETWORK:
  Residual capacity represents allowable flow adjustment

 A7_INTEGRALITY:
  Classical single-commodity network-flow models with integral data admit integral extreme-point solutions

 A8_DUALITY:
  Node potentials, cuts or related dual structures provide bounds and optimality conditions
}

REASONING {

 R1_NETWORK_PROBLEM_EXTRACTION {
  INPUT = operational_description
  IDENTIFY = nodes
  IDENTIFY = arcs
  IDENTIFY = directions
  IDENTIFY = capacities
  IDENTIFY = costs
  IDENTIFY = supplies_and_demands
  RETURN = structured_network
 }

 R2_PROBLEM_CLASSIFICATION {
  INPUT = structured_network
  CLASSIFY = shortest_path_max_flow_min_cut_min_cost_flow_transportation_assignment_transshipment_multicommodity_or_network_design
  RETURN = network_problem_class
 }

 R3_SHORTEST_PATH_REASONING {
  INPUT = graph_source_target_arc_weights
  IF all_weights_nonnegative
   APPLY = DijkstraAlgorithm
  ELSE
   APPLY = BellmanFordAlgorithm
  RETURN = shortest_path_and_distance
 }

 R4_MAX_FLOW_REASONING {
  INPUT = capacitated_network_source_sink
  INITIALISE = feasible_flow
  BUILD = residual_network
  WHILE augmenting_path_exists
   AUGMENT = flow
   UPDATE = residual_network
  RETURN = maximum_flow_and_corresponding_cut
 }

 R5_MIN_COST_FLOW_REASONING {
  INPUT = supplies_demands_capacities_costs
  INITIALISE = feasible_flow
  APPLY = network_simplex_successive_shortest_path_or_primal_dual method
  UPDATE = potentials_and_reduced_costs
  RETURN = minimum_cost feasible flow
 }

 R6_TRANSPORTATION_REASONING {
  INPUT = supply_nodes_demand_nodes_cost_matrix
  FORM = bipartite_flow model
  SOLVE = transportation_or_min_cost_flow method
  RETURN = shipment_plan
 }

 R7_ASSIGNMENT_REASONING {
  INPUT = agents_tasks_cost_or_benefit matrix
  FORM = one_to_one bipartite matching model
  SOLVE = Hungarian_network_flow_or_assignment algorithm
  RETURN = assignment
 }

 R8_MULTICOMMODITY_REASONING {
  INPUT = multiple_source_destination commodities
  ENFORCE = commodity_flow conservation
  SHARE = arc capacities
  SOLVE = LP_MIP_decomposition_or_approximation
  RETURN = multicommodity_flow profile
 }

 R9_NETWORK_DESIGN_REASONING {
  INPUT = optional_arcs_fixed_costs_capacities_and_demands
  INTRODUCE = binary_activation variables
  FORM = mixed_integer_network model
  RETURN = network_design_solution
 }

 R10_OPTIMALITY_AND_SENSITIVITY {
  INPUT = network_solution
  CHECK = feasibility
  CHECK = reduced_cost_or_cut optimality
  ANALYSE = capacity_and_cost sensitivity
  RETURN = network_certificate_and_sensitivity profile
 }
}

CONSTRAINTS {
 C1 = "Node-balance sign conventions must remain consistent."
 C2 = "Arc direction must be respected."
 C3 = "Capacities and lower bounds must be compatible."
 C4 = "Dijkstra's algorithm requires nonnegative arc weights."
 C5 = "Negative cycles can make shortest-path or min-cost formulations unbounded."
 C6 = "Residual-network updates must preserve feasibility."
 C7 = "Multicommodity integrality is not guaranteed by classical single-commodity integrality results."
 C8 = "Fixed-charge network design generally requires integer variables."
 C9 = "Disconnected networks can make demand infeasible."
 C10 = "Sensitivity interpretations must respect active paths, cuts and basis structure."
}

SEMANTIC_EQUIVALENCE {
 "NetworkOptimisation" <=> "NetworkOptimization"
 "ShortestPath" <=> "MinimumCostPath"
 "MaximumFlow" <=> "MaxFlow"
 "MinimumCostFlow" <=> "MinCostFlow"
 "ResidualNetwork" <=> "ResidualGraph"
 "NodePotential" <=> "NetworkDualPotential"
 "FlowConservation" <=> "NodeBalance"
}

VALIDATION {
 V1 = "Node and arc sets are complete."
 V2 = "Arc directions are explicit."
 V3 = "Capacities are valid."
 V4 = "Costs use consistent units."
 V5 = "Flow conservation is satisfied."
 V6 = "Supplies and demands balance when required."
 V7 = "Algorithm assumptions match arc-weight structure."
 V8 = "Residual capacities are correctly updated."
 V9 = "Optimality certificate matches the problem class."
 V10 = "Integral and fractional solution status are distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 NETWORK_OPTIMISATION_DEFINITION = 0.99
 SHORTEST_PATH_REASONING = 0.99
 MAX_FLOW_REASONING = 0.99
 MIN_COST_FLOW_REASONING = 0.99
 TRANSPORTATION_REASONING = 0.99
 ASSIGNMENT_REASONING = 0.99
 MULTICOMMODITY_REASONING = 0.97
 NETWORK_DESIGN_REASONING = 0.97
 SENSITIVITY_REASONING = 0.98

 POLICY =
  "Reduce confidence when network topology, directions, capacities, supplies, demands, costs, commodity structure, lower bounds or algorithm assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  NetworkOptimisationReasoning,
  ShortestPathReasoning,
  MaximumFlowReasoning,
  MinimumCutReasoning,
  MinimumCostFlowReasoning,
  TransportationReasoning,
  AssignmentReasoning,
  TransshipmentReasoning,
  MulticommodityFlowReasoning,
  NetworkDesignReasoning,
  ResidualNetworkReasoning,
  NodePotentialReasoning,
  NetworkDualityReasoning,
  SensitivityAnalysis,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "network optimisation" -> NetworkOptimisation
  "network optimization" -> NetworkOptimisation
  "shortest path" -> ShortestPath
  "maximum flow" -> MaximumFlow
  "max flow" -> MaximumFlow
  "minimum cut" -> MinimumCut
  "minimum-cost flow" -> MinimumCostFlow
  "min-cost flow" -> MinimumCostFlow
  "residual network" -> ResidualNetwork
  "network simplex" -> NetworkSimplex
 }

 INTERPRETATION_ORDER = [
  detect_network_optimisation_context,
  identify nodes_arcs_directions_capacities_costs_supplies_demands_sources_sinks_and_commodities,
  classify shortestPath_maxFlow_minCut_minCostFlow_transportation_assignment_transshipment_multicommodity_or_networkDesign problem,
  construct flow_balance_capacity_and_cost model,
  select graph_algorithm_network_simplex_linear_programming_or_integer_programming pathway,
  solve network problem,
  verify flow_conservation_capacity_and_optimality conditions,
  analyse cuts_potentials_reduced_costs_and_sensitivity,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("network optimisation")
  OR optimisation_defined_over_nodes_and_arcs
  THEN activate(NetworkOptimisationOntology)

 E2:
  IF objective_is_minimum_path_cost
  THEN route to shortest_path reasoning

 E3:
  IF objective_is_maximum_source_sink throughput
  THEN route to max_flow_and_min_cut reasoning

 E4:
  IF supplies_demands_and_arc_costs_present
  THEN route to minimum_cost_flow

 E5:
  IF bipartite_source_destination structure
  THEN consider transportation_or_assignment model

 E6:
  IF multiple commodities_share capacities
  THEN classify multicommodity flow

 E7:
  IF optional_arcs_or_fixed_activation costs present
  THEN classify network_design_and_route to integer programming

 E8:
  IF residual_negative_cycle_exists_in_min_cost context
  THEN improve flow_or_detect modelling issue

 E9:
  IF optimality_claimed
  THEN verify cut_duality_reduced_cost_or_primal_dual certificate
}

RECURSION {
 ENTRY = NetworkOptimisation

 EXPAND(NetworkOptimisation) -> [
  Network,
  Graph,
  DirectedGraph,
  UndirectedGraph,
  Node,
  Arc,
  Edge,
  SourceNode,
  SinkNode,
  SupplyNode,
  DemandNode,
  TransshipmentNode,
  Capacity,
  ArcCapacity,
  LowerBound,
  UpperBound,
  ArcCost,
  Flow,
  FeasibleFlow,
  Circulation,
  Path,
  SimplePath,
  Cycle,
  Cut,
  MinimumCut,
  ShortestPath,
  LongestPath,
  MaximumFlow,
  MinimumCostFlow,
  MinCostCirculation,
  TransportationProblem,
  AssignmentProblem,
  TransshipmentProblem,
  MulticommodityFlow,
  NetworkDesign,
  CapacitatedNetworkDesign,
  FixedChargeNetworkDesign,
  RoutingProblem,
  ResidualNetwork,
  AugmentingPath,
  NodePotential,
  ReducedCost,
  FlowConservation,
  CutCapacity,
  Duality,
  IntegralityProperty,
  NetworkSimplex,
  DijkstraAlgorithm,
  BellmanFordAlgorithm,
  FloydWarshallAlgorithm,
  FordFulkersonAlgorithm,
  EdmondsKarpAlgorithm,
  SuccessiveShortestPath
 ]

 EXPAND(PathProblems) -> [
  ShortestPath,
  LongestPath,
  DijkstraAlgorithm,
  BellmanFordAlgorithm,
  FloydWarshallAlgorithm
 ]

 EXPAND(FlowProblems) -> [
  MaximumFlow,
  MinimumCut,
  MinimumCostFlow,
  Circulation,
  TransportationProblem,
  AssignmentProblem,
  TransshipmentProblem,
  MulticommodityFlow
 ]

 EXPAND(NetworkDesignProblems) -> [
  CapacitatedNetworkDesign,
  FixedChargeNetworkDesign,
  ArcSelection,
  CapacityExpansion,
  ConnectivityConstraint
 ]

 STOP_CONDITION =
  "Stop when the network topology, capacities, costs, supplies, demands, flow equations, problem class, selected algorithm, feasibility, optimality certificate and sensitivity are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Operations Research"

 IMMEDIATE_CONTEXTS = [
  "Operations Research Ontology",
  "Graph Theory Ontologies",
  "Linear Programming Ontology",
  "Integer Programming Ontology"
 ]

 RELATED_ONTOLOGIES = [
  "Operations Research Ontology",
  "Operations Research",
  "Graph Theory Ontologies",
  "Linear Programming Ontology",
  "Integer Programming Ontology",
  "Resource Allocation Ontology",
  "Scheduling Ontology",
  "Transportation Problem Ontologies",
  "Assignment Problem Ontologies",
  "Routing Ontologies",
  "Combinatorial Optimisation Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Network Optimisation -> Operations Research Ontology for operational decision semantics",
  "Network Optimisation -> Graph Theory for nodes, arcs, paths, cuts and connectivity",
  "Network Optimisation -> Linear Programming for continuous flow models",
  "Network Optimisation -> Integer Programming for network design and discrete routing",
  "Network Optimisation -> Resource Allocation for capacity distribution",
  "Network Optimisation -> Scheduling for time-expanded network models",
  "Network Optimisation -> Transportation and Assignment for bipartite flow structures",
  "Network Optimisation -> Routing for path and tour selection",
  "Network Optimisation -> Combinatorial Optimisation for discrete graph complexity",
  "Network Optimisation -> Scientific Computing for large sparse network problems"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible network problem classes, algorithms or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve node-arc graph semantics.",
  "Preserve flow-conservation semantics.",
  "Preserve capacity semantics.",
  "Preserve path-versus-flow distinction.",
  "Preserve residual-network semantics.",
  "Preserve max-flow min-cut duality.",
  "Preserve network-integrality qualifications.",
  "Preserve machine-readable network-optimisation semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Network optimisation solves graph-structured decision problems involving paths, flows, capacities, costs, supplies and demands."

 SHORTEST_PATH_SUMMARY =
  "Shortest-path problems seek minimum-cost routes between nodes."

 MAX_FLOW_SUMMARY =
  "Maximum-flow problems seek the greatest feasible throughput from a source to a sink."

 MIN_CUT_SUMMARY =
  "A minimum cut has the smallest total crossing capacity separating source from sink."

 MIN_COST_FLOW_SUMMARY =
  "Minimum-cost flow satisfies network balances and capacities while minimising total arc cost."

 RESIDUAL_SUMMARY =
  "Residual networks represent the remaining ability to increase or reverse existing flows."

 DUALITY_SUMMARY =
  "Cuts, node potentials and reduced costs provide dual interpretations and optimality certificates."

 INTEGRALITY_SUMMARY =
  "Classical single-commodity network-flow models with integral data often admit integral optimal solutions."

 DESIGN_SUMMARY =
  "Network-design problems add decisions about which links or capacities should exist."
}

FLOW {
 INPUT
 -> detect_network_optimisation_context
 -> identify network_nodes_arcs_directions_capacities_lower_bounds_costs_sources_sinks_supplies_demands_and_commodities
 -> classify shortest_path_max_flow_min_cut_min_cost_flow_circulation_transportation_assignment_transshipment_multicommodity_or_network_design problem
 -> construct graph_and_flow_conservation model
 -> select Dijkstra_BellmanFord_FloydWarshall_FordFulkerson_EdmondsKarp_networkSimplex_successiveShortestPath_LP_or_MIP method
 -> solve_or_augment network solution
 -> verify capacity_flow_conservation_supply_demand_and_path conditions
 -> derive residual_network_cuts_potentials_reduced_costs_or_dual certificate
 -> analyse sensitivity_to arc_costs_capacities_and_supplies
 -> route to operations_research_ontology graph_theory linear_programming integer_programming resource_allocation scheduling transportation assignment routing combinatorial_optimisation_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Network Optimisation Ontology defines optimisation over graph-structured systems. It supports directed and undirected networks, nodes, arcs, capacities, costs, supplies, demands, flow conservation, paths, cuts, shortest paths, maximum flow, minimum cut, minimum-cost flow, circulation, transportation, assignment, transshipment, multicommodity flow, network design, residual networks, augmenting paths, node potentials, reduced costs, network simplex, classical graph algorithms, integrality and duality-aware optimality reasoning."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-NETWORK-OPTIMISATION-ONTOLOGY-V1"
}

}

END_FLOW
Privacy Policy
Site Map
Kireth Research
38 Thorndale Croft, Wetwang, Driffield
East Riding of Yorkshire YO25 9XZ
Telephone:
01377 236594
Designed By
Kireth Web Design
Audio Explainer RSS Feed