Branch and Bound Ontology

FLOW ALGEBRA
BRANCH AND BOUND ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Algorithmic Mathematics
Version: 1.0 | Date: 2026-10-11 | Language: en-GB
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/branch-and-bound-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)

1. PURPOSE AND SCOPE
Define a typed, verifiable model of branch-and-bound algorithms for finite combinatorial optimisation, including search-space partitioning, admissible bounds, incumbent solutions, pruning, node selection, and proof of optimality.

2. FORMAL SIGNATURE
flow BranchAndBoundOntology v1.0
sort Problem, FeasibleSolution, PartialState, SearchNode, ObjectiveValue, Bound, Incumbent, Frontier, Certificate, Strategy
relation EXTENDS(PartialState, PartialState)
relation REPRESENTS(SearchNode, PartialState)
relation CHILD_OF(SearchNode, SearchNode)
relation FEASIBLE(FeasibleSolution, Problem)
relation COMPLETES(FeasibleSolution, PartialState)
relation BOUNDS(Bound, SearchNode)
relation PRUNED(SearchNode, Reason)
relation EXPANDS(SearchNode)
relation OPTIMAL(FeasibleSolution, Problem)
relation CERTIFIES(Certificate, Claim)

3. PROBLEM MODEL
Given a finite feasible set F and objective f: F -> R, solve min_{x in F} f(x).
For maximisation, reverse the bound and comparison directions throughout.
A search node n denotes a subset F(n) of candidate feasible solutions.
The root r denotes F(r) = F.
Branching produces children c_1,...,c_k satisfying union_i F(c_i) = F(n).
Children may overlap, but a disjoint partition is often preferable to avoid duplicate work.

4. TYPED ENTITIES
Problem: {id, sense:min|max, objective, constraints, finite_domain}
SearchNode: {id, parent_id?, depth:int, state, status:open|expanded|pruned|terminal}
Bound: {node_id, value:real, direction:lower|min|upper|max, admissible:bool, method}
Incumbent: {solution?, objective_value?, feasibility_verified:bool}
Frontier: {open_nodes:set<SearchNode>, selection_strategy}
PruneReason: {infeasible, bound_dominated, exhausted}
Certificate: {incumbent_solution, incumbent_value, frontier_exhausted, bound_proofs}

5. RELATIONSHIPS AND INVARIANTS
PARENT(n,c) => CHILD_OF(c,n).
CHILD_OF(c,n) => F(c) subseteq F(n).
Every candidate represented by a nonterminal node remains covered by its children after branching.
For minimisation, admissible LB(n) <= min_{x in F(n)} f(x) whenever F(n) is nonempty.
For maximisation, admissible UB(n) >= max_{x in F(n)} f(x) whenever F(n) is nonempty.
The incumbent is always a verified feasible solution, never merely a relaxation result.
For minimisation, incumbent values are monotonically nonincreasing as better solutions are found.
For maximisation, incumbent values are monotonically nondecreasing.

6. EXECUTION FLOW (MINIMISATION)
INPUT finite optimisation problem P, admissible lower-bound function LB, branching operator BRANCH.
INITIALISE frontier = {root(P)}, incumbent = none.
WHILE frontier not empty:
  n := SELECT(frontier); remove n from frontier.
  IF F(n) is provably empty: PRUNE(n, infeasible); CONTINUE.
  b := LB(n).
  IF incumbent exists AND b >= incumbent.value:
    PRUNE(n, bound_dominated); CONTINUE.
  IF n represents a complete feasible solution x:
    IF incumbent absent OR f(x) < incumbent.value: incumbent := (x,f(x)).
    MARK_TERMINAL(n); CONTINUE.
  children := BRANCH(n).
  ASSERT union_{c in children} F(c) = F(n).
  ADD children to frontier.
OUTPUT incumbent if present, otherwise infeasible, with exhaustion certificate.

7. INFERENCE RULES
R1 FEASIBLE(x,P) AND incumbent absent => SET_INCUMBENT(x,f(x)).
R2 FEASIBLE(x,P) AND f(x) < incumbent.value => REPLACE_INCUMBENT(x,f(x)) [min].
R3 PROVED_EMPTY(F(n)) => PRUNED(n,infeasible).
R4 ADMISSIBLE_LOWER_BOUND(n,b) AND incumbent.value <= b => PRUNED(n,bound_dominated) [min].
R5 TERMINAL(n,x) AND FEASIBLE(x,P) => EVALUATE(x).
R6 FRONTIER_EMPTY AND ALL_NODES_RESOLVED AND incumbent feasible => OPTIMAL(incumbent,P).
R7 FRONTIER_EMPTY AND ALL_NODES_RESOLVED AND no incumbent => INFEASIBLE(P).
R8 For max, replace lower bounds by admissible upper bounds and prune when UB(n) <= incumbent.value.

8. NODE SELECTION STRATEGIES
Depth-first: select deepest open node; typically modest frontier memory.
Breadth-first: select shallowest open node; may use substantial memory.
Best-bound: select minimum lower bound for minimisation (maximum upper bound for maximisation).
Hybrid: combine depth, bound, and heuristic priority without compromising bound admissibility.
Selection strategy affects efficiency, not correctness if all unresolved nodes are eventually processed.

9. BOUND CONSTRUCTION
Relaxation bound: optimise over a superset of F(n) for minimisation to obtain a valid lower bound.
Combinatorial bound: use problem-specific inequalities proven valid for every completion.
Heuristic candidate: produces an incumbent only after verifying feasibility; heuristic objective estimates are not automatically valid bounds.
Tighter admissible bounds can increase pruning but may cost more computation.

10. WORKED EXAMPLE: 0/1 KNAPSACK (MAXIMISATION)
Capacity C=5; items (weight,value): A=(2,6), B=(3,7), C=(4,8).
Choose x_i in {0,1}; maximise 6x_A+7x_B+8x_C subject to 2x_A+3x_B+4x_C <=5.
Feasible candidates: {}, {A}:6, {B}:7, {C}:8, {A,B}:13.
Pairs {A,C} and {B,C}, and triple {A,B,C}, violate capacity.
Branch on item inclusion/exclusion; use fractional-knapsack relaxation as an admissible upper bound.
The feasible incumbent {A,B} has value 13.
After proving every remaining node's upper bound <=13 or infeasibility, certify optimum 13.

11. CORRECTNESS CONDITIONS
Coverage: branching preserves all feasible completions.
Soundness: infeasibility and bound-pruning decisions use valid proofs.
Feasibility: every incumbent satisfies the original constraints.
Termination: finite branching tree and no repeated expansion of the same unresolved node, or another proven well-founded termination measure.
Optimality: on frontier exhaustion, no unexamined feasible solution can improve the incumbent.
If termination or bound validity is not established, report a candidate/best-known solution rather than a proof of optimality.

12. COMPLEXITY
Worst-case explored nodes can be exponential in the number of discrete decisions.
Bounding quality, branching order, incumbent discovery, and node selection determine practical performance.
Memory ranges from approximately search depth for suitable depth-first implementations to frontier size for best-bound/breadth-first implementations.
Do not assert polynomial-time worst-case complexity for general NP-hard optimisation problems.

13. SEMANTIC EQUIVALENCE AND DISTINCTIONS
SEMANTIC_EQUIVALENCE: branch-and-bound ~ exact optimisation search with valid bounding and pruning.
RELATED_TO: backtracking, implicit enumeration, integer programming, combinatorial optimisation, search trees.
DIFFERENT_FROM: greedy algorithm (commits to local choices without exhaustive optimality certification).
DIFFERENT_FROM: dynamic programming (reuses overlapping subproblem solutions through state caching).
DIFFERENT_FROM: beam search (may discard nodes without safe optimality bounds).
DIFFERENT_FROM: branch-and-cut (adds valid cutting planes to the branch-and-bound framework).

14. VALIDATION TESTS
T1: Each generated child must be a subset of its parent state space.
T2: Union of children must cover every parent completion.
T3: All pruning bounds must have the correct direction and proof of admissibility.
T4: Incumbent solutions must pass independent feasibility checks.
T5: A minimisation node with LB < incumbent must not be pruned solely by bound dominance.
T6: Frontier exhaustion must account for every expanded, pruned, or terminal node.
T7: For the knapsack example, optimum is 13 with A and B.
T8: If no feasible incumbent exists, distinguish unproven search from certified infeasibility.

15. CONFIDENCE
Formal correctness confidence: high conditional on coverage, admissibility, feasibility, and termination proofs.
Instance solution confidence: certified only when exhaustive resolution and certificate checks pass.
Heuristic estimates and empirical performance: instance-dependent, not mathematical guarantees.

16. FLOW_HASH
FLOW_HASH.algorithm: SHA-256
FLOW_HASH.scope: UTF-8 canonical file bytes, excluding the FLOW_HASH.value line if one is added.
FLOW_HASH.value: NOT_COMPUTED
FLOW_HASH.note: Compute and populate at publication; do not invent a digest.

17. UPDATE_MODEL
UPDATE_MODEL.version: 1.0
UPDATE_MODEL.policy: semantic-versioning
UPDATE_MODEL.triggers: new proof rules, new bounds, revised entities, corrected examples, ontology cross-links.
UPDATE_MODEL.requirements: preserve canonical URL; rerun validation tests; record revision history.

18. AI_CONSUMPTION
AI_CONSUMPTION.mode: structured-reasoning-reference
AI_CONSUMPTION.tasks: classify algorithms, check pruning safety, explain optimality, map search-state relationships.
AI_CONSUMPTION.require_provenance: true
AI_CONSUMPTION.do_not_conflate: feasible incumbent with certified optimum; heuristic score with admissible bound.
AI_CONSUMPTION.output: {problem, sense, incumbent, bounds, frontier_status, certificate_status, confidence}

END FLOW ALGEBRA