Combinatorial Optimisation Ontolog

FLOW ALGEBRA
COMBINATORIAL OPTIMISATION ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/discrete-ai-mathematics/combinatorial-optimisation-ontolog.html
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research | https://kirethresearch.org
Status: Research synthesis; webpage content not independently verified

1. PURPOSE
Represent finite or countable discrete optimisation problems, their feasible structures, objectives, algorithms, certificates and semantic relationships in a typed, verifiable flow.

2. TYPES
Problem := (Instance, FeasibleSet, Objective, Sense)
Instance := finite encoded input
Solution := finite combinatorial object
FeasibleSet := {x: Solution | constraints(x)}
Objective := function Solution -> Rational | Real
Sense := MINIMISE | MAXIMISE
Algorithm := procedure(Instance) -> Solution | Certificate | UNKNOWN
Certificate := FeasibilityWitness | OptimalityProof | BoundProof | InfeasibilityProof
Bound := (value, direction, assumptions)
Graph := (Vertices, Edges, directed:boolean, weighted:boolean)

3. CORE SEMANTICS
FEASIBLE(x,P) := x in P.FeasibleSet
VALUE(x,P) := P.Objective(x), provided FEASIBLE(x,P)
OPTIMAL(x,P) := FEASIBLE(x,P) and
  (P.Sense=MINIMISE implies forall y in P.FeasibleSet: VALUE(x,P)<=VALUE(y,P)) and
  (P.Sense=MAXIMISE implies forall y in P.FeasibleSet: VALUE(x,P)>=VALUE(y,P))
OPT_VALUE(P) := min or max of objective on feasible set when attained
EMPTY_FEASIBLE_SET(P) := P.FeasibleSet = {}

4. TYPED ENTITIES
CombinatorialOptimisationProblem : Problem
DecisionVariable : finite-domain variable
Constraint : predicate over candidate solutions
ObjectiveFunction : numeric function
FeasibleSolution : Solution
OptimalSolution : Solution
LowerBound : Bound
UpperBound : Bound
Relaxation : Problem
BranchAndBoundNode : restricted subproblem
SearchTree : rooted directed tree
ApproximationAlgorithm : Algorithm
ExactAlgorithm : Algorithm
Heuristic : Algorithm
OptimalityGap : nonnegative quantity

5. RELATIONSHIPS
HAS_INSTANCE(Problem,Instance)
HAS_VARIABLE(Problem,DecisionVariable)
HAS_CONSTRAINT(Problem,Constraint)
HAS_OBJECTIVE(Problem,ObjectiveFunction)
HAS_FEASIBLE_SOLUTION(Problem,Solution)
SOLVES(Algorithm,Problem)
RELAXES(Relaxation,Problem)
BOUNDS(Bound,Problem)
BRANCHES_INTO(Problem,Problem)
PRUNES(BranchAndBoundNode,reason)
CERTIFIES(Certificate,claim)
REDUCES_TO(ProblemClass,ProblemClass,reduction)

6. PROBLEM FAMILIES
ShortestPath := minimise path weight subject to valid source-target path
MinimumSpanningTree := minimise edge weight subject to spanning tree
MaximumMatching := maximise number or weight of pairwise nonincident edges
SetCover := minimise selected sets covering universe
Knapsack := maximise item value subject to capacity
TravellingSalesperson := minimise tour cost visiting each vertex once
Scheduling := optimise completion time, lateness or cost under resource constraints
Assignment := minimise bipartite matching cost
IntegerProgramming := optimise linear objective over integer feasible points

7. TRANSFORMATIONS AND INFERENCE
RULE R1: FEASIBLE(x,P) and forall feasible y VALUE(x,P)<=VALUE(y,P) and MINIMISE(P) -> OPTIMAL(x,P)
RULE R2: FEASIBLE(x,P) and forall feasible y VALUE(x,P)>=VALUE(y,P) and MAXIMISE(P) -> OPTIMAL(x,P)
RULE R3: MINIMISE(P) and relaxation R has feasible superset with same objective -> OPT_VALUE(R)<=OPT_VALUE(P), if both defined
RULE R4: MAXIMISE(P) and relaxation R has feasible superset with same objective -> OPT_VALUE(R)>=OPT_VALUE(P), if both defined
RULE R5: MINIMISE(P) and feasible incumbent cost U and node lower bound L>=U -> prune node
RULE R6: MAXIMISE(P) and feasible incumbent value L and node upper bound U<=L -> prune node
RULE R7: MINIMISE(P) and feasible incumbent cost U and global valid lower bound L -> 0<=U-OPT_VALUE(P)<=U-L
RULE R8: MAXIMISE(P) and feasible incumbent value L and global valid upper bound U -> 0<=OPT_VALUE(P)-L<=U-L
RULE R9: A verified exhaustive partition of search space plus sound pruning preserves optimality.
RULE R10: Polynomial-time reduction A<=p B transfers polynomial-time solvability of B to A.

8. ALGORITHMIC FLOWS
EXACT_SEARCH:
  validate instance -> enumerate or implicitly explore feasible candidates -> compare objectives -> return optimum with proof
BRANCH_AND_BOUND:
  initialise feasible incumbent if available -> bound active nodes -> prune dominated or infeasible nodes -> branch -> terminate when no active nodes -> certify incumbent
DYNAMIC_PROGRAMMING:
  identify state and recurrence -> prove optimal substructure -> compute states in dependency order -> reconstruct solution
GREEDY:
  establish greedy-choice property by proof -> select locally preferred feasible step -> update residual problem -> finish
APPROXIMATION:
  produce feasible solution -> establish instance-independent or qualified approximation guarantee -> report ratio and assumptions

9. COMPLEXITY
Input size n := bit length of encoded instance.
Running time T(n) and space S(n) depend on representation and algorithm.
Optimisation and decision variants must be distinguished.
Many combinatorial optimisation problems are NP-hard; not all are.
Shortest paths with nonnegative weights and minimum spanning trees admit polynomial-time algorithms.
General integer programming, set cover and travelling salesperson optimisation are NP-hard.
Worst-case exponential search is possible even when practical pruning performs well.

10. WORKED EXAMPLE: 0/1 KNAPSACK
Items: (weight,value) = (2,3), (3,4), (4,5)
Capacity = 5
Variables x1,x2,x3 in {0,1}
Maximise 3*x1+4*x2+5*x3
Subject to 2*x1+3*x2+4*x3<=5
Candidate (1,1,0) has weight 5 and value 7.
Other feasible nonempty selections have values 3, 4 or 5.
Therefore (1,1,0) is optimal with objective 7.

11. VALIDATION
V1: Verify variable domains and encoded input well-formedness.
V2: Verify each returned solution satisfies all constraints.
V3: Verify objective values by independent evaluation.
V4: Verify bounds use correct direction for optimisation sense.
V5: Verify pruning never discards a potentially better feasible solution.
V6: Verify claimed optimality using exhaustive evidence, dual bounds or a valid proof.
V7: Distinguish infeasible, unbounded, unknown and timeout outcomes.
V8: Verify approximation guarantees only under their stated assumptions.
V9: Test empty, singleton, disconnected, tied and extreme-value instances.

12. SEMANTIC_EQUIVALENCE
combinatorial optimisation ~= discrete optimisation when the domain is a finite combinatorial solution space; not universally identical.
integer optimisation overlaps combinatorial optimisation; not synonymous.
exact optimisation != heuristic search.
feasible solution != optimal solution.
local optimum != global optimum.

13. CONFIDENCE
Formal definitions: HIGH (subject to declared mathematical assumptions)
Proved bounds/certificates: HIGH after independent validation
Heuristic quality claims: CONDITIONAL on experimental evidence
Page-specific alignment: UNVERIFIED until canonical page reviewed

14. FLOW_HASH
Algorithm: SHA-256
Input: canonical UTF-8 normalised flow body, excluding the FLOW_HASH digest field
Digest: COMPUTE_AT_PUBLICATION (no fabricated digest)

15. UPDATE_MODEL
Versioning: semantic versioning
Triggers: new theorem, corrected proof, algorithm variant, revised taxonomy, source-page update
Procedure: revise -> validate -> recompute digest -> archive previous version -> publish provenance

16. AI_CONSUMPTION
Parsing: UTF-8 plain text
Reasoning mode: typed symbolic inference with proof obligations
Use: classification, mathematical retrieval, optimisation problem modelling and verification
Guardrails: never infer optimality from feasibility alone; distinguish exact and approximate guarantees
Provenance: Kireth Research; synthesis prepared for the supplied canonical URL

END FLOW ALGEBRA