Linear Programming Solver Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Linear Programming Solver Ontology within the Kireth Research Semantic Library. A linear programming solver computes an optimum of a linear objective subject to linear equality and inequality constraints and variable bounds. This ontology supports standard, canonical and inequality forms, feasible regions, simplex and revised simplex methods, dual simplex, interior-point methods, primal-dual methods, presolve, scaling, basis management, degeneracy, infeasibility, unboundedness, duality, complementary slackness, sensitivity analysis, numerical tolerances, sparse linear algebra, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = LinearProgrammingSolver
 ENTITY_CLASS = LinearOptimisationSolutionFramework
 PRIMARY_CONTEXT = ComputationalOptimisation
 DEFINITION = "A linear programming solver is a numerical algorithm that minimises or maximises a linear objective over decision variables subject to linear constraints and bounds."
 SYMBOLIC_FORMS = [
  "min_x c^T x subject_to A x <= b",
  "max_x c^T x subject_to A x <= b",
  "min_x c^T x subject_to A_eq x=b_eq, l<=x<=u",
  "dual: max_y b^T y subject_to A^T y<=c"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for linear programs, feasible polyhedra, simplex bases, primal-dual optimality, interior-point systems, infeasibility and unboundedness certificates, sensitivity analysis, numerical tolerances and verification."
}

SCOPE {
 INCLUDE = [
  LinearProgrammingSolver,LinearProgramming,LP,LinearOptimisation,
  LinearObjective,ObjectiveVector,DecisionVariable,VariableBound,
  LowerBound,UpperBound,FreeVariable,NonnegativeVariable,
  LinearConstraint,EqualityConstraint,InequalityConstraint,
  LessThanConstraint,GreaterThanConstraint,ConstraintMatrix,
  ConstraintVector,RightHandSide,FeasibleSet,FeasibleRegion,
  Polyhedron,Polytope,ExtremePoint,Vertex,BasicFeasibleSolution,
  StandardForm,CanonicalForm,SlackVariable,SurplusVariable,
  ArtificialVariable,ConstraintNormalisation,
  PrimalProblem,DualProblem,PrimalVariable,DualVariable,
  DualMultiplier,ShadowPrice,ReducedCost,ComplementarySlackness,
  WeakDuality,StrongDuality,DualityGap,
  PrimalFeasibility,DualFeasibility,Optimality,
  SimplexMethod,PrimalSimplex,RevisedSimplexMethod,DualSimplexMethod,
  TwoPhaseSimplex,PhaseOne,PhaseTwo,BigMMethod,
  Basis,BasisMatrix,NonbasicVariable,BasicVariable,
  EnteringVariable,LeavingVariable,Pivot,PivotElement,
  RatioTest,MinimumRatioTest,PricingRule,DantzigRule,
  BlandRule,SteepestEdgePricing,DevexPricing,
  Degeneracy,DegeneratePivot,Cycling,AntiCyclingRule,
  InteriorPointMethod,BarrierMethod,LogBarrier,
  PrimalDualInteriorPoint,PathFollowingMethod,CentralPath,
  BarrierParameter,ComplementarityMeasure,
  NewtonSystem,KKTSystem,NormalEquations,AugmentedSystem,
  PredictorCorrector,MehrotraPredictorCorrector,
  Presolve,Postsolve,Scaling,RowScaling,ColumnScaling,
  RedundantConstraint,FixedVariable,SingletonRow,SingletonColumn,
  BoundTightening,ConstraintAggregation,
  SparseMatrix,SparseLinearAlgebra,SparseFactorisation,
  LUFactorisation,CholeskyFactorisation,QRFactorisation,
  BasisFactorisation,BasisUpdate,ForrestTomlinUpdate,
  EtaMatrix,Refactorisation,FillIn,
  ConditionNumber,Conditioning,IllConditioning,
  NumericalTolerance,FeasibilityTolerance,OptimalityTolerance,
  PivotTolerance,ZeroTolerance,ResidualTolerance,
  PrimalResidual,DualResidual,ComplementarityResidual,
  InfeasibleProblem,PrimalInfeasibility,DualInfeasibility,
  UnboundedProblem,InfeasibilityCertificate,UnboundedRay,
  FarkasLemma,FarkasCertificate,
  OptimalBasis,MultipleOptima,AlternativeOptimum,
  UniqueOptimum,OptimalFace,
  SensitivityAnalysis,PostOptimalAnalysis,
  ObjectiveCoefficientRange,RightHandSideRange,
  AllowableIncrease,AllowableDecrease,
  ShadowPriceSensitivity,ParametricLinearProgramming,
  WarmStart,HotStart,ColdStart,
  Crossover,InteriorPointCrossover,
  SolverConfiguration,SolverStatus,Optimal,Infeasible,
  Unbounded,IterationLimit,TimeLimit,NumericalFailure,
  IterationCount,SimplexIteration,BarrierIteration,
  FunctionEvaluationNotApplicable,
  ComputationalComplexity,MemoryComplexity,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,
  Overflow,Underflow,Verification,Benchmarking,
  ReferenceSolution,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  QuadraticProgrammingWithNonzeroQuadraticObjective,
  NonlinearProgrammingWithNonlinearConstraints,
  IntegerProgrammingWithIntegralityAsPrimarySemantics,
  GeneralEquationSolvingWithoutLinearObjective
 ]
 DISAMBIGUATION_RULE = "When the objective and all constraints are linear in continuous decision variables, interpret the computational task as linear programming."
}

CORE_CONCEPTS {
 LinearProgramming = "Optimisation of a linear objective over a polyhedral feasible set."
 BasicFeasibleSolution = "Feasible solution associated with a valid simplex basis."
 SimplexMethod = "Vertex-based method that moves between basic feasible solutions while improving or preserving the objective."
 RevisedSimplexMethod = "Simplex implementation using basis factorisation rather than explicit tableau updates."
 DualSimplexMethod = "Simplex method maintaining dual feasibility while repairing primal infeasibility."
 InteriorPointMethod = "Method approaching optimality through the interior of the feasible region using barrier and primal-dual equations."
 ReducedCost = "Marginal optimality measure for a nonbasic variable relative to a current basis."
 ShadowPrice = "Optimal dual multiplier measuring local objective sensitivity to a constraint right-hand side."
}

RELATIONS {
 LinearProgrammingSolver --is_child_of--> ComputationalOptimisation
 LinearProgrammingSolver --solves--> LinearProgramming
 LinearProgramming --has--> LinearObjective
 LinearProgramming --has--> LinearConstraint
 LinearConstraint --defines--> FeasibleRegion
 FeasibleRegion --is_type_of--> Polyhedron
 SimplexMethod --moves_between--> BasicFeasibleSolution
 BasicFeasibleSolution --is_defined_by--> Basis
 RevisedSimplexMethod --uses--> BasisFactorisation
 DualSimplexMethod --maintains--> DualFeasibility
 PrimalDualInteriorPoint --uses--> KKTSystem
 BarrierMethod --follows--> CentralPath
 StrongDuality --relates--> PrimalAndDualOptimalValues
 ComplementarySlackness --characterises_under_feasibility--> PrimalDualOptimality
 Presolve --simplifies--> LinearProgramming
 Scaling --improves_often--> NumericalConditioning
 FarkasCertificate --certifies--> Infeasibility
 UnboundedRay --certifies--> Unboundedness
 SensitivityAnalysis --uses--> OptimalBasisAndDualSolution
 Verification --checks--> LinearProgrammingResult
}

OPERATORS {
 PRIMAL_LP(c,A,b,l,u) := min c^T*x subject_to A*x<=b and l<=x<=u
 DUAL_LP(c,A,b) := max b^T*y subject_to A^T*y<=c and y<=0_for_leq_convention
 REDUCED_COST(c_N,A_N,y) := r_N=c_N-A_N^T*y
 PRIMAL_RESIDUAL(A,x,b) := constraint_violation(A*x,b)
 DUAL_RESIDUAL(A,y,s,c) := c-A^T*y-s
 DUALITY_GAP(c,x,b,y) := c^T*x-b^T*y
 SIMPLEX_PIVOT(B,N,enter,leave) := updated_basis
 BARRIER_OBJECTIVE(x,mu) := c^T*x-mu*sum_i log(slack_i)
 KKT_RESIDUAL(x,y,s) := combine(primal_residual,dual_residual,complementarity)
}

AXIOMS {
 A1 = "A linear program has a linear objective and linear equality or inequality constraints."
 A2 = "The feasible region of a linear program is convex and polyhedral."
 A3 = "If a finite optimum exists, at least one optimum occurs at an extreme point for standard finite-dimensional LPs."
 A4 = "Strong duality equates primal and dual optimal objective values under standard feasible finite optimum conditions."
 A5 = "Complementary slackness links primal and dual optimal solutions."
 A6 = "Simplex and interior-point methods solve the same LP through different computational geometries."
 A7 = "Infeasibility and unboundedness are distinct termination states and should carry certificates when available."
 A8 = "LP results require explicit feasibility, optimality, numerical-tolerance and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(objective_vector,constraint_matrix,right_hand_side,bounds,optimisation_direction,scale)
 R2_NORMALISE = convert_constraints_and_bounds_to_solver_representation
 R3_PRESOLVE = remove_fixed_variables_redundancy_and_tighten_bounds
 R4_SCALE = apply_row_and_column_scaling_if_required
 R5_METHOD = select(primal_simplex,dual_simplex,interior_point_or_hybrid_strategy)
 R6_INITIALISE = construct_basis_or_primal_dual_start
 R7_ITERATE = perform_simplex_pivot_or_primal_dual_Newton_step
 R8_MONITOR = track(primal_residual,dual_residual,duality_gap,degeneracy_conditioning_and_progress)
 R9_TERMINATE = classify(optimal,infeasible,unbounded,limit_or_numerical_failure)
 R10_VALIDATE = verify_primal_feasibility_dual_feasibility_complementarity_certificates_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Degeneracy can cause simplex stalling and cycling without suitable anti-cycling rules."
 C2 = "Ill-conditioned bases can degrade simplex accuracy."
 C3 = "Interior-point Newton systems can become poorly conditioned near optimality."
 C4 = "Poor scaling can distort feasibility and optimality tests."
 C5 = "Presolve reductions must be reversible through postsolve."
 C6 = "A tiny primal residual alone does not establish optimality."
 C7 = "A tiny duality gap alone is insufficient when primal or dual feasibility is poor."
 C8 = "Loose tolerances can report numerically questionable solutions as optimal."
 C9 = "Very tight tolerances can cause excessive iterations or numerical failure."
 C10 = "Floating-point certificates require tolerance-aware interpretation."
}

SEMANTIC_EQUIVALENCE {
 "LinearProgrammingSolver" <=> "LPSolver"
 "LinearProgramming" <=> "LP"
 "RevisedSimplexMethod" <=> "RevisedSimplex"
 "DualSimplexMethod" <=> "DualSimplex"
 "PrimalDualInteriorPoint" <=> "PrimalDualBarrierMethod"
 "FarkasCertificate" <=> "InfeasibilityCertificateInLPContext"
}

VALIDATION {
 V1 = "Objective coefficients are explicit."
 V2 = "Constraint matrix, right-hand sides and senses are documented."
 V3 = "Variable bounds are documented."
 V4 = "Optimisation direction is explicit."
 V5 = "Presolve and scaling settings are documented where relevant."
 V6 = "Primal and dual residuals are reported."
 V7 = "Duality gap or equivalent optimality metric is reported."
 V8 = "Infeasibility or unboundedness certificates are checked where available."
 V9 = "Sensitivity results are interpreted relative to the final optimal basis or dual solution."
 V10 = "Results are reproducible under documented arithmetic and solver settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 LINEAR_PROGRAMMING_DEFINITION = 0.99
 SIMPLEX_REASONING = 0.99
 DUAL_SIMPLEX_REASONING = 0.99
 INTERIOR_POINT_REASONING = 0.99
 DUALITY_REASONING = 0.99
 INFEASIBILITY_REASONING = 0.99
 SENSITIVITY_REASONING = 0.98
 POLICY = "Reduce confidence when constraint senses, variable bounds, scaling, tolerances, presolve transformations, basis conditioning or termination certificates are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,LinearProgrammingReasoning,
  SimplexReasoning,RevisedSimplexReasoning,DualSimplexReasoning,
  InteriorPointReasoning,PrimalDualReasoning,
  BasisReasoning,PivotReasoning,DegeneracyReasoning,
  DualityReasoning,ComplementarySlacknessReasoning,
  PresolveReasoning,ScalingReasoning,SparseFactorisationReasoning,
  InfeasibilityReasoning,UnboundednessReasoning,
  FarkasCertificateReasoning,SensitivityAnalysisReasoning,
  SolverStatusReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "linear programming solver" -> LinearProgrammingSolver
  "LP solver" -> LinearProgrammingSolver
  "linear program" -> LinearProgramming
  "revised simplex" -> RevisedSimplexMethod
  "dual simplex" -> DualSimplexMethod
  "primal-dual interior point" -> PrimalDualInteriorPoint
 }
}

EXECUTION_RULES {
 E1 = "If objective and constraints are linear in continuous variables, activate LinearProgrammingSolverOntology."
 E2 = "Normalise constraint senses and variable bounds before solver execution."
 E3 = "Use presolve to simplify the model while preserving recoverability through postsolve."
 E4 = "Use scaling when coefficient magnitudes create poor numerical conditioning."
 E5 = "Use primal or dual simplex when basis information or warm starts are valuable."
 E6 = "Use interior-point methods for large sparse LPs when their numerical structure is favourable."
 E7 = "Monitor primal feasibility, dual feasibility and duality gap together."
 E8 = "Distinguish optimality, infeasibility, unboundedness, resource limits and numerical failure."
 E9 = "Validate final primal-dual conditions, certificates, sensitivity information and reproducibility."
}

RECURSION {
 ENTRY = LinearProgrammingSolver
 EXPAND(LinearProgrammingSolver) -> [
  LinearProgramming,LP,LinearObjective,ObjectiveVector,DecisionVariable,
  VariableBound,LinearConstraint,EqualityConstraint,InequalityConstraint,
  ConstraintMatrix,RightHandSide,FeasibleRegion,Polyhedron,ExtremePoint,
  BasicFeasibleSolution,StandardForm,SlackVariable,SurplusVariable,
  ArtificialVariable,PrimalProblem,DualProblem,DualMultiplier,
  ShadowPrice,ReducedCost,ComplementarySlackness,WeakDuality,
  StrongDuality,DualityGap,PrimalFeasibility,DualFeasibility,
  SimplexMethod,PrimalSimplex,RevisedSimplexMethod,DualSimplexMethod,
  TwoPhaseSimplex,PhaseOne,PhaseTwo,Basis,BasisMatrix,BasicVariable,
  NonbasicVariable,EnteringVariable,LeavingVariable,Pivot,RatioTest,
  PricingRule,BlandRule,SteepestEdgePricing,Degeneracy,Cycling,
  InteriorPointMethod,BarrierMethod,PrimalDualInteriorPoint,
  CentralPath,BarrierParameter,KKTSystem,NormalEquations,
  PredictorCorrector,MehrotraPredictorCorrector,Presolve,Postsolve,
  Scaling,BoundTightening,SparseMatrix,SparseFactorisation,
  LUFactorisation,CholeskyFactorisation,BasisFactorisation,
  BasisUpdate,Conditioning,FeasibilityTolerance,OptimalityTolerance,
  PrimalResidual,DualResidual,ComplementarityResidual,
  InfeasibleProblem,UnboundedProblem,FarkasCertificate,UnboundedRay,
  MultipleOptima,SensitivityAnalysis,ShadowPriceSensitivity,
  WarmStart,Crossover,SolverStatus,Optimal,Infeasible,Unbounded,
  IterationLimit,TimeLimit,NumericalFailure,FloatingPointArithmetic,
  Verification,Benchmarking,ReferenceSolution,Reproducibility
 ]
 EXPAND(LinearProgrammingFamilies) -> [
  PrimalSimplexMethods,
  RevisedSimplexMethods,
  DualSimplexMethods,
  InteriorPointMethods,
  PresolveAndScaling,
  InfeasibilityAndUnboundednessDetection,
  SensitivityAndPostOptimalAnalysis,
  SparseLargeScaleLinearProgramming
 ]
 STOP_CONDITION = "Stop when LP formulation, bounds, presolve, scaling, algorithm, feasibility, optimality, certificates and verification are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Optimisation Ontology"
 RELATED_ONTOLOGIES = [
  "Computational Optimisation Ontology",
  "Optimisation Computation",
  "Linear Solver Ontology",
  "Sparse Matrix Ontology 2",
  "Dense Matrix Ontology",
  "LU Decomposition Ontology",
  "Cholesky Decomposition Ontology",
  "QR Decomposition Ontology",
  "Numerical Linear Algebra Ontology 2",
  "Numerical Stability Ontology 2",
  "Numerical Error Ontology",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology",
  "Scientific Computing Ontology 2"
 ]
 ROUTE_RULES = [
  "Linear Programming Solver -> Computational Optimisation for parent semantics",
  "Linear Programming Solver -> Linear Solver for basis and KKT systems",
  "Linear Programming Solver -> Sparse Matrix for large constraint matrices",
  "Linear Programming Solver -> LU Decomposition for simplex basis factorisation",
  "Linear Programming Solver -> Cholesky Decomposition for interior-point normal equations",
  "Linear Programming Solver -> Numerical Linear Algebra for conditioning and factorisation",
  "Linear Programming Solver -> Numerical Stability for tolerance and conditioning semantics",
  "Linear Programming Solver -> Numerical Error for residual interpretation",
  "Linear Programming Solver -> Scientific Computing for large sparse implementation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible LP algorithms, presolve rules or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve primal-versus-dual distinction.",
  "Preserve feasibility-versus-optimality distinction.",
  "Preserve simplex-versus-interior-point distinction.",
  "Preserve basis-versus-nonbasis variable distinction.",
  "Preserve infeasible-versus-unbounded distinction.",
  "Preserve exact-model-versus-tolerance-aware numerical status distinction.",
  "Preserve presolve-model-versus-original-model distinction.",
  "Preserve machine-readable linear-programming-solver semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A linear programming solver optimises a linear objective subject to linear constraints and variable bounds."
 SIMPLEX_SUMMARY = "Simplex methods move between basic feasible solutions using basis updates, pricing and pivot rules."
 DUAL_SUMMARY = "Primal and dual feasibility, complementary slackness and strong duality characterise optimal LP solutions."
 INTERIOR_POINT_SUMMARY = "Primal-dual interior-point methods follow a central path by solving sparse KKT or normal-equation systems."
 STATUS_SUMMARY = "LP solvers distinguish optimal, infeasible, unbounded, iteration-limit, time-limit and numerical-failure outcomes."
 SENSITIVITY_SUMMARY = "Optimal bases and dual multipliers support local post-optimal and sensitivity analysis."
 VALIDATION_SUMMARY = "LP results should be checked through primal and dual residuals, duality gap, certificates, tolerance settings and reproducibility."
}

FLOW {
 INPUT
 -> detect_linear_programming_solver_context
 -> identify_objective_constraint_matrix_rhs_constraint_senses_variable_bounds_and_direction
 -> normalise_LP_representation
 -> apply_presolve_and_bound_tightening
 -> scale_rows_columns_and_objective_if_required
 -> select_primal_simplex_dual_simplex_interior_point_or_hybrid_strategy
 -> initialise_basis_or_primal_dual_iterates
 -> perform_simplex_pivots_or_primal_dual_Newton_iterations
 -> monitor_primal_residual_dual_residual_duality_gap_degeneracy_conditioning_and_progress
 -> classify_optimal_infeasible_unbounded_limit_or_numerical_failure_status
 -> recover_original_model_solution_through_postsolve
 -> if_optimal_compute_reduced_costs_shadow_prices_and_sensitivity_information
 -> validate_primal_dual_conditions_certificates_and_reproducibility
 -> route_to_related_optimisation_linear_solver_sparse_matrix_factorisation_stability_error_convergence_and_scientific_computing_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Linear Programming Solver Ontology defines numerical solution of linear optimisation problems with linear objectives, constraints and variable bounds. It supports standard and canonical LP forms, feasible polyhedra and basic feasible solutions, primal, revised and dual simplex methods, two-phase initialisation, basis factorisation and updates, pricing, pivoting, degeneracy and anti-cycling rules, primal-dual interior-point and predictor-corrector methods, presolve, scaling and postsolve, sparse KKT and basis systems, primal and dual residuals, duality gaps, infeasibility and unboundedness certificates, Farkas reasoning, multiple optima, sensitivity and post-optimal analysis, warm starts, crossover, numerical tolerances, finite precision, verification, benchmarking and reproducibility."
}

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

}

END_FLOW