Optimisation Problem Ontology

FLOW ALGEBRA
OPTIMISATION PROBLEM ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Computational Mathematical Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/computational-mathematical-entities/optimisation-problem-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed formalisation; source page wording not independently verified.
Version: 1.0 | Date: 2026-10-14

1. PURPOSE
Represent an optimisation problem as typed entities, objective functions, admissible decision domains, constraints, solutions and verifiable optimality claims. Distinguish feasibility, local optimality, global optimality and algorithmic approximation.

2. TYPE SYSTEM
TYPE OptimisationProblem
TYPE DecisionVariable
TYPE VariableDomain
TYPE ObjectiveFunction
TYPE Constraint
TYPE ConstraintSet
TYPE FeasibleRegion
TYPE FeasiblePoint
TYPE CandidateSolution
TYPE LocalOptimum
TYPE GlobalOptimum
TYPE ApproximateSolution
TYPE OptimalityCertificate
TYPE Algorithm
TYPE SolverResult
TYPE NumericalTolerance
TYPE ProvenanceRecord
ENUM Direction = {MINIMISE, MAXIMISE}
ENUM SolverStatus = {OPTIMAL_CERTIFIED, FEASIBLE_UNCERTIFIED, INFEASIBLE_CERTIFIED, UNBOUNDED_CERTIFIED, UNKNOWN, ERROR}

3. FORMAL DEFINITION
Let X be a nonempty ambient decision domain, f:X -> extended real values, and constraints c_i:X -> {true,false}.
F := {x in X | for all i, c_i(x)=true}.
MINIMISE: find x* in F such that f(x*) <= f(x) for all x in F.
MAXIMISE: find x* in F such that f(x*) >= f(x) for all x in F.
If F is empty, the problem is infeasible.
If F is nonempty but no feasible point attains the infimum/supremum, an optimum need not exist.
An unbounded objective is distinct from an unattained finite optimum.

4. ENTITY RELATIONSHIPS
OptimisationProblem --HAS_VARIABLE--> DecisionVariable
DecisionVariable --HAS_DOMAIN--> VariableDomain
OptimisationProblem --HAS_OBJECTIVE--> ObjectiveFunction
OptimisationProblem --HAS_DIRECTION--> Direction
OptimisationProblem --HAS_CONSTRAINT_SET--> ConstraintSet
ConstraintSet --CONTAINS--> Constraint
ConstraintSet --DEFINES--> FeasibleRegion
CandidateSolution --ASSIGNS--> DecisionVariable
CandidateSolution --SATISFIES--> Constraint
CandidateSolution --EVALUATED_BY--> ObjectiveFunction
SolverResult --PRODUCED_BY--> Algorithm
SolverResult --REPORTS--> CandidateSolution
OptimalityCertificate --JUSTIFIES--> GlobalOptimum
SolverResult --HAS_PROVENANCE--> ProvenanceRecord

5. MATHEMATICAL INVARIANTS
INV-01: A feasible solution belongs to the variable domain and satisfies every hard constraint.
INV-02: A global optimum is feasible and no feasible point improves its objective value.
INV-03: Every global optimum is locally optimal relative to the feasible set, but not conversely.
INV-04: An infeasible problem has no feasible solution.
INV-05: A solver's termination is not by itself a proof of global optimality.
INV-06: For minimisation, a certified lower bound L and feasible incumbent U satisfy L <= f* <= U, where f* is the optimal value, when a finite optimum exists.
INV-07: Equality and inequality constraints require explicit comparison semantics and numeric tolerances when evaluated approximately.
INV-08: Convex objective over convex feasible region yields global optimality for any local minimiser, subject to the standard convexity assumptions.

6. EXECUTABLE FLOW ALGEBRA (DECLARATIVE PSEUDOCODE)
flow "OptimisationProblemValidation" v1.0
  input: problem, candidate?, certificate?
  require: typed(problem.variables)
  require: defined(problem.objective)
  require: problem.direction in {MINIMISE, MAXIMISE}
  domain_check := validate_variable_domains(problem)
  constraint_check := validate_constraint_signatures(problem)
  if not(domain_check and constraint_check): return INVALID_MODEL
  if candidate is null: return MODEL_VALID_CANDIDATE_NOT_SUPPLIED
  feasible := within_domains(candidate) and all_constraints_satisfied(candidate)
  if not feasible: return CANDIDATE_INFEASIBLE
  value := evaluate(problem.objective, candidate)
  if certificate is null: return FEASIBLE_UNCERTIFIED(value)
  certified := independently_verify_certificate(problem, candidate, certificate)
  if certified: return OPTIMAL_CERTIFIED(value)
  return FEASIBLE_UNCERTIFIED(value)
end

flow "OptimisationProblemSolve" v1.0
  input: problem, solver, settings
  validate(problem)
  result := solver.run(problem, settings)
  attach(result, solver_version, settings, model_hash, timestamp)
  if result.candidate exists: validate_feasibility(result.candidate)
  if result.certificate exists: independently_verify_certificate(result.certificate)
  return result with status and evidence
end

7. INFERENCE RULES
R1: feasible(x) AND certified_global_bound(x) => globally_optimal(x).
R2: violates_any_hard_constraint(x) => NOT feasible(x).
R3: convex_minimisation(problem) AND local_minimiser(x) => global_minimiser(x).
R4: feasible(x) AND feasible(y) AND f(x)<f(y) AND direction=MINIMISE => x dominates y in objective value.
R5: solver_reports_optimal(x) AND NOT verified_certificate => reported_optimality, NOT independently_certified_optimality.
R6: empty_feasible_region(problem) => infeasible(problem), only when emptiness is established by sound evidence.

8. SEMANTIC DISTINCTIONS
Optimisation problem != feasibility problem: feasibility may omit an objective.
Local optimum != global optimum.
Optimal value != optimal decision vector.
Constraint satisfaction != optimality.
Exact solution != floating-point approximation.
Infeasible != unbounded != solver failure.
Objective function != loss function in every domain, although a loss may serve as an objective.

9. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  mathematical_definition: 1.00 (standard formal specification)
  model_correctness: evidence-dependent
  numerical_feasibility: tolerance-dependent
  optimality_claim: certificate-dependent
  inferred_semantic_mapping: provenance-dependent
Record assumptions, constraint conventions, solver versions, input data provenance and numerical precision.

10. SEMANTIC_EQUIVALENCE
"optimisation problem" ~ "optimization problem" [spelling equivalence]
"minimisation problem" ~ "minimization problem" [spelling equivalence]
"mathematical programme" ~ "mathematical program" [contextual equivalence]
"optimal solution" != "feasible solution"
"local minimum" != "global minimum"

11. FLOW_HASH
Canonicalise the ontology record using stable UTF-8 encoding, sorted entity identifiers and relationship keys, normalised whitespace, and a declared schema version. Compute FLOW_HASH := SHA-256(canonical_record). The hash is a reproducible integrity identifier, not a proof of mathematical correctness. No digest is asserted here without executing the canonicalisation and hashing process.

12. UPDATE_MODEL
On revision: increment version; preserve source URL and prior FLOW_HASH; record changes to definitions, type constraints, mathematical assumptions, inference rules and certificate validation; invalidate downstream derived claims when their assumptions change.

13. AI_CONSUMPTION
Expose machine-readable entity types, formal constraints, objective direction, solution status, evidence of feasibility and optimality, confidence and provenance. AI systems must not infer that a reported solver result is globally optimal without sufficient supporting evidence. Preserve ambiguity when modelling assumptions are missing.

14. QUALITY CHECKS
QC-01: All referenced variables are declared and typed.
QC-02: Objective direction is explicit.
QC-03: Hard constraints are evaluated consistently.
QC-04: Candidate objective is evaluated only after domain validation.
QC-05: Numerical tolerances and units are recorded.
QC-06: Certified and uncertified solver statuses remain distinct.
QC-07: Infeasible, unbounded and unknown statuses are not conflated.
QC-08: Cross-ontology links include Objective Function, Decision Variable, Constraint Set, Feasible Region, Exact Solution, Approximate Solution, Numerical Method and Convergence Criterion.

END FLOW ALGEBRA