1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
;;; Copyright (c) 2026 Nicholas Vermeulen
;;; SPDX-License-Identifier: AGPL-3.0-or-later
;; simplex.lisp — tableau simplex (Bland's rule) for tiny dense LPs, with an
;; exhaustive cross-check against brute-force vertex enumeration. Pure Lisp,
;; zero interpreter changes.
;;
;; Solves maximize c·x subject to A x ≤ b, x ≥ 0, with b ≥ 0 (so the
;; all-slack origin is a feasible start — a DOCUMENTED restriction that avoids
;; a phase-1; infeasible-start LPs are out of scope, not silently mishandled).
;; Result is a certificate: `(status optimal) (x V) (z Z)` or `(status unbounded)`.
;; Bland's rule (smallest-index entering/leaving) guarantees termination — no
;; cycling on degenerate problems.
;;
;; THE VERIFICATION BITE — the oracle is honest, not the algorithm's word:
;; `lp-brute` independently enumerates every vertex of the feasible polygon and
;; takes the best; `verify-simplex-agrees` proves, over EVERY tiny LP in a
;; declared finite grid, that simplex's objective equals brute's within ε and
;; their unbounded/optimal status agrees. A simplex bug shows up as a
;; counterexample LP — the brute enumerator is the trusted reference.
;;
;; PORTABILITY: simplex pivots produce non-dyadic fractions, so the exhaustive
;; check compares objectives within ε (never prints a raw pivoted float); the
;; known-answer fixtures are chosen with integer optima so their printed z is
;; exact. Only + - * / — no libm.
;;
;; CLAIM DISCIPLINE: "simplex agrees with brute vertex enumeration on the
;; declared tiny LPs (2 vars, 2 constraints, entries in a small set)". NEVER an
;; industrial-LP claim, NEVER "optimal for large / ill-conditioned problems".
; 1e-6 feasibility / compare tol
;; ── List helpers ──────────────────────────────────────────────────────────
;; ── Tableau simplex ───────────────────────────────────────────────────────
;; Tableau: m constraint rows then 1 objective row; columns are
;; [x_1..x_n | s_1..s_m | rhs]. Objective row starts as [-c | 0 | 0]; a negative
;; entry there means the objective can still improve.
;; Entering column: smallest index j with objective-row reduced cost < -eps (Bland).
;; Leaving row: min-ratio rhs/col over positive column entries; Bland ties by
;; smallest basic-variable index. Returns -1 if the column has no positive entry
;; (⇒ unbounded).
;; Pivot on (row, col): normalize the pivot row, eliminate the column elsewhere.
;; a[k] - f·b[k], elementwise (Rusty has no dotted pairs — recurse two lists).
;; ── Brute-force vertex enumeration (2 vars) — the trusted oracle ──────────
;; Unbounded (with A ≥ 0, b ≥ 0): a variable with c_j>0 whose column is all 0.
;; Solve the 2×2 [p q][r s]·x = [u v]; Nil if singular.
;; Every candidate vertex = intersection of two of the four boundary lines
;; {con1, con2, x1=0, x2=0}. Feasible ones satisfy all constraints and x≥0.
;; ── Exhaustive cross-check: simplex ≡ brute over a tiny LP grid ───────────
;; For every (a11 a12 a21 a22 b1 b2) with c fixed, simplex and brute must agree:
;; same unbounded/optimal status and, when optimal, objective within ε.
;; The false claim "every optimum is 0" must be refused with a witness LP.