Integer Programming Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Integer Programming Ontology within the Kireth Research Semantic Library. Integer programming studies optimisation problems in which some or all decision variables are restricted to integer values. This ontology supports pure integer programming, binary programming, mixed-integer programming, linear and nonlinear integer models, branch-and-bound, branch-and-cut, cutting planes, relaxations, valid inequalities, integrality gaps, node bounds, fathoming, incumbent solutions, presolve, heuristics, decomposition, sensitivity limits and relationships with linear programming, convex optimisation, combinatorial optimisation, operations research and scientific computing.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Integer Programming Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Optimisation / Integer Programming"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/optimisation/integer-programming-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = IntegerProgramming
 SYMBOLIC_FORMS = [
  "min c^T x subject to A x <= b, x in Z^n",
  "x_i in {0,1}",
  "x_I integer, x_C continuous"
 ]
 ENTITY_CLASS = DiscreteMathematicalProgrammingFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Integer programming is optimisation in which one or more decision variables are constrained to take integer values."
 SEMANTIC_ROLE = "Provides the machine-readable framework for integrality constraints, binary decisions, mixed-integer models, relaxations, branch-and-bound, cutting planes, valid inequalities, incumbent solutions, lower and upper bounds, integrality gaps and discrete optimality certificates."
}

SCOPE {
 INCLUDE = [
  IntegerProgramming,
  IntegerProgram,
  PureIntegerProgramming,
  BinaryProgramming,
  MixedIntegerProgramming,
  MixedIntegerLinearProgramming,
  MixedIntegerNonlinearProgramming,
  IntegerVariable,
  BinaryVariable,
  ContinuousVariable,
  IntegralityConstraint,
  LogicalConstraint,
  IndicatorConstraint,
  BigMFormulation,
  LinearRelaxation,
  ConvexRelaxation,
  LagrangianRelaxation,
  BranchAndBound,
  BranchAndCut,
  BranchingRule,
  SearchTree,
  Node,
  NodeRelaxation,
  LowerBound,
  UpperBound,
  IncumbentSolution,
  Fathoming,
  CuttingPlane,
  ValidInequality,
  GomoryCut,
  CoverCut,
  CliqueCut,
  IntegralityGap,
  OptimalityGap,
  Presolve,
  PrimalHeuristic,
  LocalSearch,
  RoundingHeuristic,
  FeasibilityPump,
  Decomposition,
  BendersDecomposition,
  DantzigWolfeDecomposition,
  ColumnGeneration,
  Symmetry,
  SymmetryBreaking,
  OptimalityCertificate
 ]

 EXCLUDE_AS_PRIMARY = [
  ContinuousLinearProgrammingWithoutIntegrality,
  GenericCombinatorialSearchWithoutObjectiveFunction,
  ConstraintSatisfactionWithoutOptimisationGoal,
  DiscreteDynamicProgrammingUnlessIntegerProgrammingFormulationIsExplicit
 ]

 DISAMBIGUATION_RULE =
  "When one or more optimisation decision variables must take integer or binary values, interpret the problem as integer programming."
}

CORE_CONCEPTS {

 IntegerProgramming {
  definition = "Optimisation over decision variables with integrality restrictions."
 }

 PureIntegerProgramming {
  definition = "An integer program in which all decision variables are integer-valued."
 }

 BinaryProgramming {
  definition = "An integer program whose discrete variables are restricted to zero or one."
 }

 MixedIntegerProgramming {
  definition = "An optimisation problem containing both integer and continuous decision variables."
 }

 MixedIntegerLinearProgramming {
  symbol = "MILP"
  definition = "A mixed-integer optimisation problem with linear objective and linear constraints."
 }

 IntegerVariable {
  definition = "A decision variable restricted to integer values."
 }

 BinaryVariable {
  definition = "A decision variable restricted to the set {0,1}."
 }

 LinearRelaxation {
  definition = "A relaxation obtained by replacing integrality constraints with continuous bounds."
 }

 BranchAndBound {
  definition = "A tree-search method that partitions the feasible region and uses bounds to eliminate subproblems."
 }

 CuttingPlane {
  definition = "A valid constraint added to remove fractional solutions while preserving all integer-feasible solutions."
 }

 IncumbentSolution {
  definition = "The best known integer-feasible solution during a search."
 }

 IntegralityGap {
  definition = "The difference between an integer optimum and an optimisation relaxation bound, under a declared convention."
 }
}

RELATIONS {
 IntegerProgramming --is_special_case_of--> Optimisation
 PureIntegerProgramming --is_type_of--> IntegerProgramming
 BinaryProgramming --is_type_of--> IntegerProgramming
 MixedIntegerProgramming --is_type_of--> IntegerProgramming
 MixedIntegerLinearProgramming --is_type_of--> MixedIntegerProgramming
 MixedIntegerLinearProgramming --has_relaxation--> LinearProgramming
 IntegerVariable --has_constraint--> IntegralityConstraint
 BinaryVariable --is_type_of--> IntegerVariable
 BranchAndBound --solves--> IntegerProgram
 BranchAndCut --combines--> BranchAndBound
 BranchAndCut --combines--> CuttingPlane
 Node --has--> NodeRelaxation
 NodeRelaxation --provides--> Bound
 IncumbentSolution --provides--> FeasibleObjectiveBound
 Fathoming --removes--> SearchTreeNode
 CuttingPlane --is--> ValidInequality
 GomoryCut --is_type_of--> CuttingPlane
 CoverCut --is_type_of--> CuttingPlane
 Presolve --simplifies--> IntegerProgram
 PrimalHeuristic --searches_for--> IncumbentSolution
 BendersDecomposition --decomposes--> StructuredMixedIntegerProblem
 ColumnGeneration --supports--> LargeScaleRelaxation
 SymmetryBreaking --reduces--> RedundantSearch
}

OPERATORS {
 FORM_INTEGER_PROGRAM(objective,variables,constraints,integrality) :=
  formal_integer_optimisation_problem

 RELAX_INTEGRALITY(IP) :=
  continuous_relaxation

 CHECK_INTEGER_FEASIBILITY(x,I) :=
  all x_i are integers for i in I
  AND all_original_constraints_satisfied

 BRANCH_ON_VARIABLE(x_j,value) :=
  create child_1 with x_j <= floor(value)
  and child_2 with x_j >= ceil(value)

 UPDATE_INCUMBENT(current,candidate,objective_direction) :=
  better_integer_feasible_solution

 FATHOM_BY_BOUND(node_bound,incumbent_value) :=
  true when node cannot improve incumbent
  under objective_direction convention

 FATHOM_BY_INFEASIBILITY(node_relaxation) :=
  true when node relaxation infeasible

 FATHOM_BY_INTEGRALITY(node_solution) :=
  true when relaxation solution is integer feasible
  after incumbent update

 INTEGRALITY_GAP(incumbent,bound) :=
  declared_absolute_or_relative difference

 ADD_VALID_INEQUALITY(model,cut) :=
  model_with_cut_preserving_integer_feasible_set

 BIG_M_LOGIC(binary,M,constraint) :=
  algebraic_activation_or_deactivation
  under valid_M bounds

 BENDERS_CUT(master,subproblem_dual_information) :=
  feasibility_or_optimality_cut
}

DEFINITIONS {
 D1 = "Integer programming imposes discrete value restrictions on decision variables."
 D2 = "Binary variables represent yes/no, on/off or selection decisions."
 D3 = "Continuous relaxations provide bounds but can admit fractional solutions."
 D4 = "Branch-and-bound explores a search tree while pruning provably irrelevant nodes."
 D5 = "Cutting planes strengthen relaxations without removing integer-feasible solutions."
 D6 = "Branch-and-cut combines tree search with cutting-plane generation."
 D7 = "An incumbent is the best known feasible discrete solution."
 D8 = "Integrality gaps measure the strength of relaxations relative to discrete optima."
 D9 = "Big-M formulations require valid and preferably tight M values."
 D10 = "Symmetry can create redundant search and may benefit from symmetry-breaking constraints."
}

AXIOMS {
 A1_INTEGRALITY:
  IntegerProgramming contains at least one integrality-constrained decision variable

 A2_FEASIBILITY:
  Integer-feasible solutions satisfy both original constraints and integrality restrictions

 A3_RELAXATION_BOUND:
  A valid relaxation provides an objective bound on the original integer problem

 A4_BRANCH_PARTITION:
  Valid branching partitions the parent node's integer-feasible region across child nodes

 A5_VALID_CUT:
  A valid inequality excludes no integer-feasible solution

 A6_FATHOMING:
  A search-tree node may be safely removed when infeasible, dominated by bound, or fully resolved

 A7_INCUMBENT:
  The incumbent objective provides a global feasible bound during search

 A8_CERTIFICATION:
  Global optimality requires closure of the search gap or another valid proof
}

REASONING {

 R1_INTEGER_MODEL_IDENTIFICATION {
  INPUT = optimisation_problem
  IDENTIFY = integer_variables
  IDENTIFY = binary_variables
  IDENTIFY = continuous_variables
  IDENTIFY = objective_and_constraints
  RETURN = integer_problem_class
 }

 R2_RELAXATION_REASONING {
  INPUT = integer_program
  DROP_OR_RELAX = integrality constraints
  SOLVE = continuous relaxation
  RETURN = lower_or_upper bound
 }

 R3_BRANCHING_REASONING {
  INPUT = fractional_relaxation_solution
  SELECT = branching_variable_or_disjunction
  CREATE = child_nodes
  RETURN = branched_search_tree
 }

 R4_BOUNDING_REASONING {
  INPUT = search_tree_node
  SOLVE = node_relaxation
  COMPARE = node_bound_with_incumbent
  RETURN = promising_or_fathomable
 }

 R5_CUT_GENERATION {
  INPUT = fractional_relaxation_solution
  IDENTIFY = violated_valid_inequality
  ADD = cut
  RESOLVE = relaxation
  RETURN = strengthened_node
 }

 R6_INCUMBENT_SEARCH {
  INPUT = relaxation_solution_or_partial_solution
  APPLY = rounding_local_search_feasibility_pump_or_domain heuristic
  IF integer_feasible_and_better
   UPDATE = incumbent
  RETURN = incumbent_status
 }

 R7_FATHOMING {
  INPUT = node_state
  IF relaxation_infeasible
   FATHOM = infeasibility
  ELSE IF bound_cannot_improve_incumbent
   FATHOM = bound
  ELSE IF relaxation_solution_integer_feasible
   UPDATE = incumbent
   FATHOM = integrality
  RETURN = node_status
 }

 R8_GAP_ANALYSIS {
  INPUT = incumbent_and_global_bound
  COMPUTE = absolute_and_or_relative gap
  IF gap <= tolerance
   RETURN = optimal_within_tolerance
  ELSE
   RETURN = continue_search
 }

 R9_FORMULATION_QUALITY {
  INPUT = model
  CHECK = BigM_tightness
  CHECK = relaxation_strength
  CHECK = symmetry
  CHECK = redundant_constraints
  RETURN = formulation_profile
 }

 R10_DECOMPOSITION_REASONING {
  INPUT = structured_large_integer_program
  IDENTIFY = complicating_variables_or_constraints
  SELECT = Benders_DantzigWolfe_column_generation_or_other decomposition
  RETURN = decomposed_solver_strategy
 }
}

CONSTRAINTS {
 C1 = "Integrality must be applied to the intended variables only."
 C2 = "Continuous relaxations must preserve all nonintegrality constraints."
 C3 = "Branching disjunctions must cover all integer-feasible possibilities."
 C4 = "Cuts must be valid for every integer-feasible solution."
 C5 = "Big-M values must be valid and should be as tight as practical."
 C6 = "Poor relaxations can cause large branch-and-bound trees."
 C7 = "Node bounds and incumbent values must use consistent objective directions."
 C8 = "Relative optimality-gap formulas require careful handling near zero objective values."
 C9 = "Heuristic solutions provide feasible bounds but not optimality proofs."
 C10 = "Solver termination due to limits must not be reported as proven optimality."
}

SEMANTIC_EQUIVALENCE {
 "IntegerProgramming" <=> "IntegerOptimisation"
 "BinaryProgramming" <=> "ZeroOneOptimisation"
 "MixedIntegerProgramming" <=> "MixedDiscreteContinuousOptimisation"
 "MILP" <=> "MixedIntegerLinearProgramming"
 "BranchAndBound" <=> "BoundedTreeSearchOptimisation"
 "CuttingPlane" <=> "ValidInequalityRelaxationStrengthening"
 "IncumbentSolution" <=> "BestKnownIntegerFeasibleSolution"
}

VALIDATION {
 V1 = "Integer and continuous variables are correctly identified."
 V2 = "Integrality constraints are correctly encoded."
 V3 = "Relaxation is a valid relaxation of the original problem."
 V4 = "Branching partitions the feasible set correctly."
 V5 = "Cuts preserve integer feasibility."
 V6 = "Incumbent solutions satisfy all original constraints."
 V7 = "Node bounds use correct objective direction."
 V8 = "Optimality gap uses a declared convention."
 V9 = "Big-M constants are valid."
 V10 = "Optimality, infeasibility and limit termination are distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 INTEGER_PROGRAMMING_DEFINITION = 0.99
 RELAXATION_REASONING = 0.99
 BRANCH_AND_BOUND_REASONING = 0.99
 CUTTING_PLANE_REASONING = 0.98
 INCUMBENT_REASONING = 0.99
 GAP_REASONING = 0.99
 FORMULATION_REASONING = 0.98
 DECOMPOSITION_REASONING = 0.97

 POLICY =
  "Reduce confidence when integrality domains, relaxation validity, branching rule, cut validity, incumbent feasibility, bound convention, Big-M validity or solver termination status are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  IntegerProgrammingReasoning,
  BinaryProgrammingReasoning,
  MixedIntegerProgrammingReasoning,
  MILPReasoning,
  RelaxationReasoning,
  BranchAndBoundReasoning,
  BranchAndCutReasoning,
  CuttingPlaneReasoning,
  ValidInequalityReasoning,
  IncumbentReasoning,
  IntegralityGapReasoning,
  BigMReasoning,
  PresolveReasoning,
  HeuristicReasoning,
  DecompositionReasoning,
  SymmetryReasoning,
  OptimalityCertification,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "integer programming" -> IntegerProgramming
  "integer optimisation" -> IntegerProgramming
  "binary programming" -> BinaryProgramming
  "0-1 programming" -> BinaryProgramming
  "mixed-integer programming" -> MixedIntegerProgramming
  "mixed integer linear programming" -> MixedIntegerLinearProgramming
  "MILP" -> MixedIntegerLinearProgramming
  "branch and bound" -> BranchAndBound
  "branch and cut" -> BranchAndCut
  "cutting plane" -> CuttingPlane
  "integrality gap" -> IntegralityGap
 }

 INTERPRETATION_ORDER = [
  detect_integer_programming_context,
  identify objective_integer_binary_continuous_variables_constraints_bounds_and_logic,
  classify pure_integer_binary_MILP_MINLP_or_other discrete optimisation structure,
  construct continuous_or_convex relaxation,
  solve relaxation_and_compute bound,
  branch_cut_or_heuristically_search,
  update incumbent_and_global bound,
  assess integrality_gap_and_search termination,
  certify optimal_infeasible_unbounded_or_limit status,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("integer programming")
  OR one_or_more_decision_variables_are_integer
  THEN activate(IntegerProgrammingOntology)

 E2:
  IF all_discrete_variables_binary
  THEN classify as BinaryProgramming

 E3:
  IF objective_and_constraints_linear
  AND both_integer_and_continuous_variables_present
  THEN classify as MixedIntegerLinearProgramming

 E4:
  IF relaxation_solution_fractional
  THEN branch_or_generate valid cuts

 E5:
  IF integer_feasible_solution_found
  THEN update incumbent_if_better

 E6:
  IF node_bound_cannot_improve_incumbent
  THEN fathom node

 E7:
  IF BigM_formulation_used
  THEN verify M_validity_and_tightness

 E8:
  IF global_gap_below_tolerance
  THEN report optimal_within_declared tolerance

 E9:
  IF time_node_or_memory_limit_reached_with_nonzero_gap
  THEN report best_known_feasible_solution_and_bound_without claiming proven optimum
}

RECURSION {
 ENTRY = IntegerProgramming

 EXPAND(IntegerProgramming) -> [
  IntegerProgram,
  PureIntegerProgramming,
  BinaryProgramming,
  MixedIntegerProgramming,
  MixedIntegerLinearProgramming,
  MixedIntegerNonlinearProgramming,
  IntegerVariable,
  BinaryVariable,
  ContinuousVariable,
  IntegralityConstraint,
  LogicalConstraint,
  IndicatorConstraint,
  BigMFormulation,
  LinearRelaxation,
  ConvexRelaxation,
  LagrangianRelaxation,
  BranchAndBound,
  BranchAndCut,
  BranchingRule,
  SearchTree,
  Node,
  NodeRelaxation,
  LowerBound,
  UpperBound,
  IncumbentSolution,
  Fathoming,
  CuttingPlane,
  ValidInequality,
  GomoryCut,
  CoverCut,
  CliqueCut,
  IntegralityGap,
  OptimalityGap,
  Presolve,
  PrimalHeuristic,
  LocalSearch,
  RoundingHeuristic,
  FeasibilityPump,
  Decomposition,
  BendersDecomposition,
  DantzigWolfeDecomposition,
  ColumnGeneration,
  Symmetry,
  SymmetryBreaking,
  OptimalityCertificate
 ]

 EXPAND(SearchTree) -> [
  RootNode,
  ChildNode,
  BranchingRule,
  NodeRelaxation,
  Bound,
  IncumbentSolution,
  Fathoming,
  NodeSelection
 ]

 EXPAND(CutFamilies) -> [
  GomoryCut,
  CoverCut,
  CliqueCut,
  MixedIntegerRoundingCut,
  FlowCoverCut,
  LiftAndProjectCut
 ]

 EXPAND(FormulationStrengthening) -> [
  Presolve,
  TightBounds,
  ValidInequality,
  SymmetryBreaking,
  StrongFormulation,
  ExtendedFormulation
 ]

 STOP_CONDITION =
  "Stop when the integrality structure, relaxation, branching or cutting strategy, incumbent, global bound, optimality gap and final discrete optimisation status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Optimisation"

 IMMEDIATE_CONTEXTS = [
  "Optimisation Ontology",
  "Linear Programming Ontology",
  "Combinatorial Optimisation Ontologies",
  "Operations Research Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Optimisation Ontology",
  "Optimisation",
  "Linear Programming Ontology",
  "Nonlinear Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Combinatorial Optimisation Ontologies",
  "Operations Research Ontologies",
  "Graph Theory Ontologies",
  "Constraint Programming Ontologies",
  "Dynamic Programming Ontologies",
  "Numerical Analysis Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Integer Programming -> Optimisation Ontology for formal optimisation semantics",
  "Integer Programming -> Linear Programming for LP relaxations and simplex/interior-point bounds",
  "Integer Programming -> Nonlinear Optimisation for mixed-integer nonlinear structure",
  "Integer Programming -> Convex Optimisation for convex relaxations",
  "Integer Programming -> Combinatorial Optimisation for discrete problem structure",
  "Integer Programming -> Operations Research for scheduling, allocation and planning models",
  "Integer Programming -> Graph Theory for network and graph-based formulations",
  "Integer Programming -> Constraint Programming for hybrid discrete reasoning",
  "Integer Programming -> Dynamic Programming for decomposable discrete states",
  "Integer Programming -> Scientific Computing for large-scale branch-and-cut implementation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible integer formulations, cuts, branching strategies or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve integrality semantics.",
  "Preserve binary-variable semantics.",
  "Preserve relaxation-bound semantics.",
  "Preserve branch-partition semantics.",
  "Preserve valid-cut semantics.",
  "Preserve incumbent-and-global-bound distinction.",
  "Preserve gap-based certification.",
  "Preserve machine-readable integer-programming semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Integer programming optimises an objective while restricting one or more decision variables to integer values."

 BINARY_SUMMARY =
  "Binary variables represent decisions restricted to zero or one."

 RELAXATION_SUMMARY =
  "Continuous relaxations remove integrality restrictions to produce objective bounds."

 BRANCH_AND_BOUND_SUMMARY =
  "Branch-and-bound partitions the discrete feasible set and prunes nodes using infeasibility, bounds or resolved integer solutions."

 CUTTING_PLANE_SUMMARY =
  "Cutting planes strengthen relaxations by removing fractional solutions without excluding integer-feasible solutions."

 INCUMBENT_SUMMARY =
  "The incumbent is the best known integer-feasible solution and provides a feasible objective bound."

 GAP_SUMMARY =
  "The integrality or optimality gap compares the incumbent with the best global relaxation bound."

 FORMULATION_SUMMARY =
  "Tight formulations, strong bounds, valid inequalities and symmetry reduction can dramatically improve solver performance."

 CERTIFICATION_SUMMARY =
  "Proven optimality requires closure of the global search gap or an equivalent mathematical certificate."
}

FLOW {
 INPUT
 -> detect_integer_programming_context
 -> identify objective_integer_binary_continuous_variables_domains_linear_or_nonlinear constraints_and_logical structure
 -> classify pure_integer_binary_MILP_MINLP_or_combinatorial formulation
 -> build continuous_convex_or_lagrangian relaxation
 -> solve relaxation_and_obtain node bound
 -> search for integer_feasible incumbent
 -> branch_on_fractional_or_disjunctive structure
 -> generate valid cuts_and_strengthen formulation when useful
 -> fathom nodes_by_infeasibility_bound_or_integrality
 -> update incumbent_global_bound_and_optimality gap
 -> if_structured apply decomposition_or_column generation
 -> classify optimal_infeasible_unbounded_or_resource_limited status
 -> route to optimisation_ontology linear_programming nonlinear_optimisation convex_optimisation combinatorial_optimisation operations_research graph_theory constraint_programming dynamic_programming numerical_analysis_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Integer Programming Ontology defines optimisation with discrete decision variables. It supports pure integer, binary, mixed-integer linear and mixed-integer nonlinear models, integrality and logical constraints, continuous and convex relaxations, branch-and-bound, branch-and-cut, cutting planes, valid inequalities, incumbents, node bounds, fathoming, optimality gaps, Big-M and indicator formulations, presolve, heuristics, symmetry reduction, Benders and Dantzig-Wolfe decomposition, column generation and global optimality certification."
}

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

}

END_FLOW