Reference · The Applied Higher-Order Functions catalogue

rainbow.algorithms.proofs.ahof.dual-simplex

The Applied Higher-Order Functions cataloguesrc/rainbow/algorithms/proofs/ahof/dual_simplex.clj1 definitions, 3 theorems

AHoF O55 Dual Simplex Method: solve a linear program by maintaining DUAL feasibility (reduced costs of the right sign) while iterating toward primal feasibility. Each pivot picks a leaving variable with negative basic value, then chooses the entering variable by the dual RATIO TEST: among eligible columns, take the one with the minimum ratio, which preserves dual feasibility. Selecting between two candidate columns by ratio is: choose-entering ra ia rb ib = if ra <= rb then ia else ib over exact-rational ratios (returning the chosen column index). Proved native and axiom-free: the ratio-test selection; a worked pivot picking the smaller-ratio column; and the certificate that the chosen ratio really is the minimum of the two (chosen <= other as native nnrat/at-most), so dual feasibility is maintained. The tableau update and eligibility screen are executable; what is proved is the dual ratio-test selection. Requires nat, audit/decide-nnrat-at-most, logic/if-data, nnrat/at-most, nnrat/decide-at-most-true-sound (all in the D63 checkpoint). Scope (measured by the kernel): this module has 3 worked instances (statements about specific values). None of its theorems is a guarantee about the algorithm for all inputs; `lein verify rainbow.algorithms.proofs.ahof.dual-simplex` prints this classification.

dual-simplex/choose-entering :
  (x₁ : ℚ≥0) (x₂ : ℕ) (x₃ : ℚ≥0) (x₄ : ℕ)
  → ℕ

dual-simplex/enters-min-ratio-column :
  → dijkstra/closer-vertex 3/2 0 1/2 1 = 1

dual-simplex/enters-first-when-smaller :
  → dijkstra/closer-vertex 1/4 0 3/4 1 = 0

dual-simplex/chosen-ratio-is-minimal :
  → 1/2 ≤ 3/2