Discrete Optimisation Ontology

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

1. PURPOSE
Represent finite or countable optimisation problems, feasible assignments, objectives, constraints, algorithms and proof obligations as typed, inspectable semantic flows.

2. TYPE SYSTEM
TYPE Problem = {variables: Set[Variable], domains: Map[Variable,Domain], constraints: Set[Constraint], objective: Objective, sense: MIN|MAX}
TYPE Variable = {id: String, domain: finite_or_countable_set}
TYPE Assignment = Map[Variable,Value]
TYPE Constraint = Predicate[Assignment]
TYPE Objective = Function[Assignment,Real]
TYPE FeasibleSet = Set[Assignment]
TYPE Bound = {value: Real, direction: LOWER|UPPER, justification: Proof}
TYPE Solution = {assignment: Assignment, objective_value: Real, feasible: Boolean}
TYPE Certificate = {kind: FEASIBILITY|OPTIMALITY|INFEASIBILITY, evidence: Any, verifier: Procedure}
TYPE Algorithm = {name: String, assumptions: Set[Predicate], termination: Predicate}

3. MATHEMATICAL SEMANTICS
P = (X,D,C,f,sense)
F(P) = {a in Product(D(x) for x in X) | forall c in C: c(a)=true}
OPT_MIN(P) = min {f(a) | a in F(P)} when minimum exists
OPT_MAX(P) = max {f(a) | a in F(P)} when maximum exists
ARGOPT(P) = {a in F(P) | f(a)=OPT(P)}
If F(P) is empty, status = INFEASIBLE.
If objective has no attained optimum, status = UNATTAINED; distinguish from infeasible.
For finite F(P), nonempty implies an attained optimum for real-valued f.

4. ENTITY RELATIONSHIPS
Problem HAS_VARIABLE Variable
Variable HAS_DOMAIN Domain
Problem IMPOSES Constraint
Constraint RESTRICTS FeasibleSet
Problem HAS_OBJECTIVE Objective
Assignment SATISFIES Constraint
Solution REALISES Assignment
Algorithm EXPLORES FeasibleSet
Bound LIMITS OptimalValue
Certificate JUSTIFIES Claim
Reduction MAPS Problem TO Problem

5. REPRESENTATION FAMILIES
Integer linear programming: integer-valued variables, linear constraints and objective.
Binary optimisation: domains subset of {0,1}.
Constraint optimisation: hard constraints plus objective.
Graph optimisation: paths, cuts, matchings, covers and spanning trees.
Combinatorial optimisation: subset, ordering, partition and assignment problems.
SAT/MaxSAT: Boolean feasibility and weighted clause satisfaction.

6. OPERATIONS
DEFINE(P): type-check variables, domains, constraints and objective.
EVALUATE(P,a): reject if a not in F(P); otherwise return f(a).
BRANCH(P,x,v): restrict domain or fix a decision consistently.
RELAX(P): enlarge feasible set or simplify constraints to obtain a justified bound.
PRUNE(node): allowed only if infeasible or bound proves no improvement over incumbent.
UPDATE_INCUMBENT(a): accept only if feasible and strictly improves objective.
VERIFY(solution): independently recompute feasibility and objective value.

7. INFERENCE RULES
R1 FEASIBILITY: [forall c in C, c(a)] => a in F(P).
R2 INFEASIBILITY: [F(P)=empty] => status(P)=INFEASIBLE.
R3 MIN BOUND: [L <= f(a) for all feasible a] => L <= OPT_MIN(P).
R4 MAX BOUND: [U >= f(a) for all feasible a] => OPT_MAX(P) <= U.
R5 MIN OPTIMALITY: [a in F(P), f(a)=L, L is valid lower bound] => a optimal.
R6 MAX OPTIMALITY: [a in F(P), f(a)=U, U is valid upper bound] => a optimal.
R7 MIN PRUNING: [node lower bound >= incumbent value] => node cannot improve incumbent.
R8 MAX PRUNING: [node upper bound <= incumbent value] => node cannot improve incumbent.
R9 RELAXATION: [F(P) subset F(R), same objective, minimisation] => OPT_MIN(R) <= OPT_MIN(P), provided both optima exist.
R10 EXACT REDUCTION: [reduction preserves feasibility and objective ordering] => optimisers may be mapped by the reduction's recovery function.

8. ALGORITHM CLASSES
Exhaustive enumeration: exact for finite domains, potentially exponential.
Dynamic programming: exact when recurrence and state compression are valid.
Branch and bound: exact when search is complete and bounds are sound.
Branch and cut: combines valid inequalities with complete branching.
Greedy method: optimal only under established structural conditions.
Local search: explores neighbours; generally no global-optimum guarantee.
Approximation: requires explicit ratio/additive-error conditions.
Heuristic/metaheuristic: reports candidate quality without unjustified optimality claims.

9. WORKED EXAMPLE: 0-1 KNAPSACK
Items: A(weight=2,value=3), B(weight=3,value=4), C(weight=4,value=5).
Capacity = 5; variables x_A,x_B,x_C in {0,1}.
Maximise 3*x_A + 4*x_B + 5*x_C.
Subject to 2*x_A + 3*x_B + 4*x_C <= 5.
Feasible combinations: {}, {A}, {B}, {C}, {A,B}.
Values: 0,3,4,5,7 respectively.
Optimal assignment: (1,1,0); objective = 7.
Certificate: enumerate all feasible subsets and compare values.

10. COMPLEXITY AND LIMITS
Many general discrete optimisation problems are NP-hard; do not generalise to every instance or subclass.
Distinguish decision, search and optimisation formulations.
Worst-case running time depends on input encoding and algorithm.
Pseudo-polynomial methods depend on numerical magnitudes, not solely bit-length.
Integrality gap applies to specified relaxations and objectives.

11. PROOF OBLIGATIONS
PO1 All variables have declared domains and consistent types.
PO2 Every reported candidate satisfies every hard constraint.
PO3 Bounds are valid for the specified optimisation sense.
PO4 Every pruning decision preserves at least one globally optimal solution unless optimum already certified.
PO5 Claimed exact algorithms terminate and cover all necessary cases.
PO6 Objective values are independently reproducible.
PO7 Approximation claims state assumptions and precise guarantee.

12. SEMANTIC EQUIVALENCE
Two formulations are optimisation-equivalent only with a specified mapping preserving feasible solutions and objective ordering (or a proven transformation of objective values).
A relaxation is not generally equivalent to its original integer problem.
Aliases: discrete optimisation ~ discrete optimization (orthographic equivalence).
Related but not identical: combinatorial optimisation, integer programming, constraint satisfaction, mathematical programming.

13. VALIDATION TESTS
TEST feasible assignment: knapsack (1,1,0) satisfies capacity and yields 7 -> PASS.
TEST infeasible assignment: knapsack (0,1,1) exceeds capacity -> REJECT.
TEST bound direction: minimisation lower bound cannot justify pruning by being below incumbent -> PASS if not pruned.
TEST empty feasible set: report INFEASIBLE, not optimum zero -> PASS.
TEST heuristic: no global optimality claim without certificate -> PASS.

14. CONFIDENCE
Formal definitions: HIGH when assumptions and types are satisfied.
Algorithmic claims: CONDITIONAL on proof obligations and implementation correctness.
Heuristic candidate quality: measured or estimated, not guaranteed.
External empirical performance: UNKNOWN unless benchmark evidence supplied.

15. FLOW HASH
FLOW_HASH_ALGORITHM: SHA-256
FLOW_HASH_INPUT: canonical UTF-8 representation of versioned flow, excluding stored hash field.
FLOW_HASH_VALUE: UNCOMPUTED (compute after final publication).

16. UPDATE MODEL
UPDATE_MODEL: semantic-versioned
Triggers: corrected theorem, refined type, new verified example, algorithmic extension, source-page revision.
On update: increment version, rerun tests, regenerate hash, preserve provenance and change log.

17. AI CONSUMPTION
AI_CONSUMPTION: ENABLED
Read typed entities before applying inference rules.
Never equate feasible with optimal.
Require explicit objective sense, constraints, assumptions and certificate for exact claims.
Return UNKNOWN where proof or evidence is missing.
Output: {problem, formulation, feasible_candidate, objective_value, bounds, guarantee, provenance, confidence}.

END FLOW ALGEBRA