Linear Programming Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Linear Programming Ontology within the Kireth Research Semantic Library. Linear programming is the optimisation of a linear objective function over a feasible region defined by linear equality and inequality constraints. This ontology supports standard and canonical forms, feasible regions, vertices, basic feasible solutions, simplex methods, duality, complementary slackness, reduced costs, shadow prices, sensitivity analysis, degeneracy, infeasibility, unboundedness, interior-point methods and relationships with convex optimisation, linear algebra, operations research and numerical optimisation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = LinearProgramming
 SYMBOLIC_FORMS = [
  "min c^T x subject to A x = b, x >= 0",
  "max c^T x subject to A x <= b"
 ]
 ENTITY_CLASS = LinearOptimisationFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Linear programming is the optimisation of a linear objective function subject to linear equality, inequality and bound constraints."
 SEMANTIC_ROLE = "Provides the machine-readable framework for linear objectives, polyhedral feasible regions, simplex structure, primal-dual relationships, complementary slackness, sensitivity, degeneracy, infeasibility and unboundedness."
}

SCOPE {
 INCLUDE = [
  LinearProgramming,
  LinearProgram,
  ObjectiveCoefficient,
  DecisionVariable,
  LinearConstraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  StandardForm,
  CanonicalForm,
  FeasibleRegion,
  Polyhedron,
  Polytope,
  ExtremePoint,
  Vertex,
  BasicSolution,
  BasicFeasibleSolution,
  Basis,
  NonbasicVariable,
  SlackVariable,
  SurplusVariable,
  ArtificialVariable,
  SimplexMethod,
  RevisedSimplexMethod,
  DualSimplexMethod,
  InteriorPointMethod,
  PrimalProblem,
  DualProblem,
  WeakDuality,
  StrongDuality,
  ComplementarySlackness,
  ReducedCost,
  ShadowPrice,
  DualVariable,
  Degeneracy,
  Cycling,
  BlandRule,
  PhaseOne,
  PhaseTwo,
  Infeasibility,
  Unboundedness,
  SensitivityAnalysis,
  OptimalityCertificate,
  FarkasLemma
 ]

 EXCLUDE_AS_PRIMARY = [
  NonlinearProgramming,
  IntegerProgrammingUnlessIntegralityRelaxed,
  QuadraticProgramming,
  GenericLinearEquationSolvingWithoutObjectiveFunction
 ]

 DISAMBIGUATION_RULE =
  "When both the objective and all explicit constraints are linear in the decision variables, interpret the optimisation problem as linear programming."
}

CORE_CONCEPTS {

 LinearProgramming {
  definition = "Optimisation of a linear objective over a polyhedral feasible set."
 }

 LinearProgram {
  definition = "A specific linear programming problem defined by objective coefficients, variables and linear constraints."
 }

 StandardForm {
  definition = "A common LP representation such as minimising c^T x subject to Ax=b and x>=0."
 }

 FeasibleRegion {
  definition = "The set of points satisfying all linear constraints."
 }

 ExtremePoint {
  definition = "A feasible point that cannot be expressed as a strict convex combination of two distinct feasible points."
 }

 BasicFeasibleSolution {
  definition = "A feasible solution associated with a basis of the constraint matrix."
 }

 Basis {
  definition = "A selected set of linearly independent columns used to define basic variables."
 }

 SimplexMethod {
  definition = "An LP algorithm moving between basic feasible solutions while improving the objective."
 }

 DualProblem {
  definition = "The linear program associated with the primal through primal-dual constraint and variable relationships."
 }

 ReducedCost {
  definition = "The marginal objective effect associated with moving a nonbasic variable away from its bound under the current basis."
 }

 ShadowPrice {
  definition = "A dual value representing local sensitivity of the optimal objective to a right-hand-side perturbation."
 }

 Degeneracy {
  definition = "A basic feasible solution in which one or more basic variables are zero."
 }
}

RELATIONS {
 LinearProgramming --is_special_case_of--> ConvexOptimisation
 LinearProgram --has--> LinearObjective
 LinearProgram --has--> LinearConstraint
 LinearConstraint --defines--> FeasibleRegion
 FeasibleRegion --is--> Polyhedron
 BoundedFeasibleRegion --is--> Polytope
 ExtremePoint --is_element_of--> FeasibleRegion
 BasicFeasibleSolution --corresponds_to--> Basis
 BasicFeasibleSolution --may_correspond_to--> ExtremePoint
 SimplexMethod --moves_between--> BasicFeasibleSolution
 SlackVariable --converts--> InequalityConstraintToEquality
 ArtificialVariable --supports--> PhaseOne
 PrimalProblem --has_associated--> DualProblem
 WeakDuality --bounds--> PrimalAndDualObjectiveValues
 StrongDuality --equates--> OptimalPrimalAndDualValues
 ComplementarySlackness --links--> PrimalAndDualOptimality
 ReducedCost --depends_on--> DualVariable
 ShadowPrice --is_interpretation_of--> DualVariable
 Degeneracy --may_cause--> Cycling
 BlandRule --prevents--> Cycling
 FarkasLemma --supports--> InfeasibilityCertificate
}

OPERATORS {
 FORM_STANDARD_LP(c,A,b) :=
  minimise c^T*x subject_to A*x=b AND x>=0

 CHECK_FEASIBLE(A,b,x) :=
  A*x=b AND x>=0
  under standard_form convention

 ADD_SLACK(a_i,x,b_i,s_i) :=
  a_i^T*x+s_i=b_i
  with s_i>=0

 BASIS_MATRIX(A,B) :=
  columns_of_A_indexed_by_B

 BASIC_SOLUTION(A_B,b) :=
  x_B=A_B^-1*b
  x_N=0
  WHEN A_B_is_nonsingular

 REDUCED_COST(c_j,a_j,c_B,A_B) :=
  c_j-c_B^T*A_B^-1*a_j
  under minimisation standard form

 SIMPLEX_DIRECTION(A_B,a_j) :=
  A_B^-1*a_j

 RATIO_TEST(x_B,d) :=
  min_i x_B_i/d_i
  over d_i>0

 DUAL_FROM_PRIMAL(c,A,b) :=
  derive_linear_dual_under_declared_sign conventions

 COMPLEMENTARY_SLACKNESS(primal_slack,dual_variable) :=
  product_is_zero_for_corresponding pairs

 OBJECTIVE_GAP(primal_value,dual_value) :=
  primal_value-dual_value
  for minimisation primal_with_consistent dual convention
}

DEFINITIONS {
 D1 = "Linear programming has a linear objective and linear constraints."
 D2 = "The feasible set of an LP is convex and polyhedral."
 D3 = "If a finite optimum exists, at least one optimum occurs at an extreme point under standard finite-dimensional LP conditions."
 D4 = "Simplex methods exploit basic feasible solutions."
 D5 = "Slack variables convert inequalities into equalities."
 D6 = "Dual variables encode bounds and sensitivity information."
 D7 = "Complementary slackness characterises primal-dual optimal pairs."
 D8 = "Degeneracy can cause zero-length simplex pivots."
 D9 = "An LP may be feasible and bounded, infeasible or unbounded."
 D10 = "Interior-point methods traverse the interior rather than the edges of the feasible polyhedron."
}

AXIOMS {
 A1_LINEARITY:
  Objective and constraints are linear in decision variables

 A2_CONVEX_FEASIBILITY:
  Linear-programming feasible regions are convex polyhedra

 A3_EXTREME_POINT_OPTIMALITY:
  If an LP has a finite optimum, an optimal extreme point exists under standard finite-dimensional assumptions

 A4_WEAK_DUALITY:
  Any dual-feasible value bounds any primal-feasible value under consistent primal-dual conventions

 A5_STRONG_DUALITY:
  If primal and dual LPs satisfy standard feasibility conditions and have finite optima, optimal objective values coincide

 A6_COMPLEMENTARY_SLACKNESS:
  Primal and dual feasible solutions are optimal iff complementary slackness holds under standard LP duality conditions

 A7_BASIS:
  A basic solution is defined by a nonsingular basis matrix

 A8_CERTIFICATION:
  Optimality, infeasibility and unboundedness can be certified by appropriate primal-dual evidence
}

REASONING {

 R1_LP_IDENTIFICATION {
  INPUT = optimisation_problem
  CHECK = objective_linearity
  CHECK = constraint_linearity
  CHECK = variable_domains
  RETURN = LP_or_not
 }

 R2_STANDARD_FORM_CONVERSION {
  INPUT = general_linear_program
  TRANSFORM = maximisation_to_minimisation_if_needed
  SPLIT = free_variables_if_needed
  ADD = slack_surplus_or_artificial variables
  RETURN = equivalent_standard_form
 }

 R3_FEASIBILITY_ANALYSIS {
  INPUT = LP
  CHECK = constraints_and_bounds
  IF no_obvious_feasible_basis
   RUN = PhaseOne_or_feasibility method
  RETURN = feasible_infeasible_or_unknown
 }

 R4_SIMPLEX_INITIALISATION {
  INPUT = standard_form_LP
  IDENTIFY = initial_basis
  IF unavailable
   CONSTRUCT = PhaseOne_problem
  RETURN = initial_basic_feasible_solution
 }

 R5_SIMPLEX_ITERATION {
  INPUT = current_basis
  COMPUTE = reduced_costs
  IF all_optimality_conditions_met
   RETURN = optimal_basis
  SELECT = entering_variable
  COMPUTE = search_direction
  APPLY = ratio_test
  IF no_leaving_variable
   RETURN = unbounded
  PIVOT = basis
  RETURN = next_basis
 }

 R6_DUALITY_ANALYSIS {
  INPUT = primal_LP
  DERIVE = dual_LP
  CHECK = primal_and_dual feasibility
  COMPUTE = objective_gap
  RETURN = duality_profile
 }

 R7_COMPLEMENTARY_SLACKNESS {
  INPUT = primal_and_dual_candidate
  CHECK = feasibility
  CHECK = complementary_products
  IF all_zero
   RETURN = optimal_pair
  ELSE
   RETURN = not_certified
 }

 R8_DEGENERACY_HANDLING {
  INPUT = simplex_basis
  DETECT = zero_basic_variables
  IF cycling_risk
   APPLY = BlandRule_or_lexicographic strategy
  RETURN = stable_pivot strategy
 }

 R9_SENSITIVITY_ANALYSIS {
  INPUT = optimal_basis
  PERTURB = objective_coefficients_or_rhs
  DETERMINE = basis_validity ranges
  INTERPRET = reduced_costs_and_shadow prices
  RETURN = sensitivity_profile
 }

 R10_INTERIOR_POINT_REASONING {
  INPUT = large_or_sparse_LP
  FORM = barrier_or_primal_dual system
  ITERATE = interior_point method
  MONITOR = primal_residual_dual_residual_and_duality gap
  RETURN = interior_solution_and_certificate
 }
}

CONSTRAINTS {
 C1 = "Linearity must hold in both objective and explicit constraints."
 C2 = "Variable-domain transformations must preserve problem equivalence."
 C3 = "A basis matrix must be nonsingular."
 C4 = "Reduced-cost sign conventions depend on minimisation/maximisation and tableau convention."
 C5 = "Degenerate pivots may fail to improve the objective."
 C6 = "Cycling prevention requires a valid anti-cycling rule."
 C7 = "Shadow prices are local sensitivity quantities, not unlimited global rates."
 C8 = "Sensitivity ranges are basis-dependent."
 C9 = "Interior-point approximate feasibility and optimality require tolerance-aware interpretation."
 C10 = "Unboundedness and infeasibility must not be conflated."
}

SEMANTIC_EQUIVALENCE {
 "LinearProgramming" <=> "LinearOptimisation"
 "LinearProgram" <=> "LinearOptimisationProblem"
 "BasicFeasibleSolution" <=> "FeasibleBasisSolution"
 "ReducedCost" <=> "NonbasicMarginalObjectiveCoefficient"
 "ShadowPrice" <=> "DualSensitivityValue"
 "SimplexMethod" <=> "VertexPivotLinearProgrammingMethod"
}

VALIDATION {
 V1 = "Objective is linear."
 V2 = "Constraints are linear."
 V3 = "Variable domains are explicit."
 V4 = "Standard-form transformations preserve equivalence."
 V5 = "Basis matrices are nonsingular."
 V6 = "Simplex ratio tests use correct sign logic."
 V7 = "Dual formulation uses consistent sign conventions."
 V8 = "Complementary slackness is applied to matching primal-dual pairs."
 V9 = "Sensitivity results remain within allowable perturbation ranges."
 V10 = "Optimal, infeasible and unbounded statuses are distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 LINEAR_PROGRAMMING_DEFINITION = 0.99
 STANDARD_FORM_REASONING = 0.99
 SIMPLEX_REASONING = 0.99
 DUALITY_REASONING = 0.99
 COMPLEMENTARY_SLACKNESS_REASONING = 0.99
 DEGENERACY_REASONING = 0.98
 SENSITIVITY_REASONING = 0.98
 INTERIOR_POINT_REASONING = 0.98

 POLICY =
  "Reduce confidence when sign conventions, variable domains, basis status, degeneracy, primal-dual feasibility, sensitivity ranges or solver tolerances are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  LinearProgrammingReasoning,
  LPFormulation,
  StandardFormConversion,
  FeasibilityReasoning,
  SimplexReasoning,
  RevisedSimplexReasoning,
  DualSimplexReasoning,
  InteriorPointReasoning,
  LPDualityReasoning,
  ComplementarySlacknessReasoning,
  ReducedCostReasoning,
  ShadowPriceReasoning,
  SensitivityAnalysis,
  InfeasibilityCertification,
  UnboundednessDetection,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "linear programming" -> LinearProgramming
  "linear optimisation" -> LinearProgramming
  "linear program" -> LinearProgram
  "LP" -> LinearProgram
  "simplex method" -> SimplexMethod
  "basic feasible solution" -> BasicFeasibleSolution
  "reduced cost" -> ReducedCost
  "shadow price" -> ShadowPrice
  "complementary slackness" -> ComplementarySlackness
  "dual simplex" -> DualSimplexMethod
 }

 INTERPRETATION_ORDER = [
  detect_linear_programming_context,
  identify objective_coefficients_decision_variables_domains_linear_constraints_and_bounds,
  convert_to_standard_or_solver_ready form,
  determine feasibility_and_initial basis_or interior point,
  select simplex_dual_simplex_or_interior_point pathway,
  solve LP,
  derive_and_check dual_solution,
  assess complementary_slackness_reduced_costs_shadow_prices_and_optimality gap,
  classify optimal_infeasible_or_unbounded status,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("linear programming")
  OR objective_and_constraints_are_linear
  THEN activate(LinearProgrammingOntology)

 E2:
  IF maximisation_problem
  THEN preserve objective_direction_or_convert consistently

 E3:
  IF inequality_constraints
  THEN add slack_or_surplus variables only under correct sign conventions

 E4:
  IF no_initial_feasible_basis
  THEN use PhaseOne_or_equivalent feasibility method

 E5:
  IF simplex_reduced_costs_satisfy optimality condition
  THEN check feasibility_before declaring optimal

 E6:
  IF ratio_test_has_no_valid_leaving_variable
  THEN classify primal_problem_as_unbounded along_entering direction

 E7:
  IF primal_and_dual_feasible_with_zero_gap
  THEN certify optimality

 E8:
  IF degeneracy_detected
  THEN consider anti_cycling pivot rule

 E9:
  IF sensitivity_requested
  THEN report validity_range_for_shadow_prices_and_reduced costs
}

RECURSION {
 ENTRY = LinearProgramming

 EXPAND(LinearProgramming) -> [
  LinearProgram,
  ObjectiveCoefficient,
  DecisionVariable,
  LinearConstraint,
  EqualityConstraint,
  InequalityConstraint,
  BoundConstraint,
  StandardForm,
  CanonicalForm,
  FeasibleRegion,
  Polyhedron,
  ExtremePoint,
  Vertex,
  BasicSolution,
  BasicFeasibleSolution,
  Basis,
  NonbasicVariable,
  SlackVariable,
  SurplusVariable,
  ArtificialVariable,
  SimplexMethod,
  RevisedSimplexMethod,
  DualSimplexMethod,
  InteriorPointMethod,
  PrimalProblem,
  DualProblem,
  WeakDuality,
  StrongDuality,
  ComplementarySlackness,
  ReducedCost,
  ShadowPrice,
  DualVariable,
  Degeneracy,
  Cycling,
  BlandRule,
  PhaseOne,
  PhaseTwo,
  Infeasibility,
  Unboundedness,
  SensitivityAnalysis,
  OptimalityCertificate,
  FarkasLemma
 ]

 EXPAND(SimplexStructure) -> [
  Basis,
  BasicVariable,
  NonbasicVariable,
  ReducedCost,
  EnteringVariable,
  LeavingVariable,
  Pivot,
  RatioTest,
  Degeneracy
 ]

 EXPAND(DualityStructure) -> [
  PrimalProblem,
  DualProblem,
  WeakDuality,
  StrongDuality,
  ComplementarySlackness,
  ShadowPrice,
  OptimalityGap
 ]

 EXPAND(StatusStructure) -> [
  Feasible,
  Optimal,
  Infeasible,
  Unbounded,
  Degenerate,
  MultipleOptima
 ]

 STOP_CONDITION =
  "Stop when the linear objective, feasible region, basis or interior-point state, primal-dual solution, optimality certificate, sensitivity and final LP status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Optimisation"

 IMMEDIATE_CONTEXTS = [
  "Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Linear Algebra Ontologies",
  "Operations Research Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Optimisation Ontology",
  "Optimisation",
  "Applied Mathematics Ontologies",
  "Convex Optimisation Ontology",
  "Linear Algebra Ontologies",
  "Matrix Ontologies",
  "Polyhedron Ontologies",
  "Convex Geometry Ontology",
  "Operations Research Ontologies",
  "Integer Programming Ontology",
  "Numerical Analysis Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Linear Programming -> Optimisation Ontology for formal optimisation semantics",
  "Linear Programming -> Convex Optimisation for convexity and duality",
  "Linear Programming -> Linear Algebra for basis systems and factorisations",
  "Linear Programming -> Polyhedra and Convex Geometry for feasible-region structure",
  "Linear Programming -> Operations Research for allocation and planning models",
  "Linear Programming -> Integer Programming when integrality constraints are introduced",
  "Linear Programming -> Numerical Analysis for solver stability and tolerances",
  "Linear Programming -> Scientific Computing for large sparse LP execution"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible LP algorithms, duality structures or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve linear objective and constraint semantics.",
  "Preserve polyhedral feasible-region semantics.",
  "Preserve basis and basic-feasible-solution semantics.",
  "Preserve simplex primal-dual semantics.",
  "Preserve complementary-slackness semantics.",
  "Preserve infeasible-versus-unbounded distinction.",
  "Preserve local sensitivity interpretation.",
  "Preserve machine-readable linear-programming semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Linear programming optimises a linear objective over a feasible region defined by linear constraints."

 FEASIBLE_REGION_SUMMARY =
  "The feasible set of a linear program is a convex polyhedron."

 EXTREME_POINT_SUMMARY =
  "A finite optimum, when one exists under standard assumptions, can be attained at an extreme point."

 SIMPLEX_SUMMARY =
  "The simplex method moves between basic feasible solutions using reduced costs, search directions and ratio tests."

 DUALITY_SUMMARY =
  "Linear-programming duality provides objective bounds, optimality certificates and sensitivity information."

 COMPLEMENTARY_SLACKNESS_SUMMARY =
  "Complementary slackness links primal slacks and dual variables at optimality."

 DEGENERACY_SUMMARY =
  "Degeneracy occurs when a basic variable is zero and can cause zero-length pivots or cycling."

 STATUS_SUMMARY =
  "An LP may be optimal, infeasible or unbounded, and these statuses require distinct certificates."

 SENSITIVITY_SUMMARY =
  "Reduced costs and shadow prices provide local information about changes to objective coefficients and constraint right-hand sides."
}

FLOW {
 INPUT
 -> detect_linear_programming_context
 -> identify linear_objective_decision_variables_domains_linear_constraints_and_bounds
 -> convert_to_standard_or_solver_ready representation
 -> construct_or_find feasible_start_using basis_or_PhaseOne
 -> classify simplex_revised_simplex_dual_simplex_or_interior_point pathway
 -> solve primal_problem
 -> derive_or_solve dual_problem
 -> verify primal_feasibility_dual_feasibility_complementary_slackness_and_objective gap
 -> identify degeneracy_multiple_optima_infeasibility_or_unboundedness
 -> perform sensitivity_analysis_if_required
 -> route to optimisation_ontology convex_optimisation linear_algebra matrix polyhedron convex_geometry operations_research integer_programming numerical_analysis_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Linear Programming Ontology defines optimisation of linear objectives under linear constraints. It supports standard and canonical forms, polyhedral feasible regions, extreme points, bases, basic feasible solutions, slack, surplus and artificial variables, simplex, revised simplex, dual simplex and interior-point methods, primal-dual theory, complementary slackness, reduced costs, shadow prices, degeneracy, cycling, Phase I/II methods, infeasibility, unboundedness, optimality certificates and sensitivity analysis."
}

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

}

END_FLOW