Revised simplex linear programming and certificates

Let $m,n$ be nonnegative integers, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The standard-form minimization linear program with data $(A,b,c)$ is $\min \{c^{\mathsf{T}}x:Ax=b,x\ge 0\}\mathrm{.}$ Its feasible set is $P(A,b)=\{x\in {\mathbb{R}}^n:Ax=b,x_j\ge 0\text{ for every }j\}$, and a feasible $x$ is optimal if $c^{\mathsf{T}}x\le c^{\mathsf{T}}z$ for every $z\in P(A,b)$. The notation $x\ge 0$ is componentwise. The revised-simplex basis algorithms on this page require a full-row-rank matrix, meaning $\mathrm{rank}(A)=m$; a rank-deficient raw system must first be reduced by exact row operations, with inconsistent rows reported as infeasible. For $m=0$, the empty system has its usual zero-dimensional interpretation.

A vector $q\in {\mathbb{R}}^m$ satisfying $A^{\mathsf{T}}q\ge 0$ and $b^{\mathsf{T}}q<0$ is called a Farkas infeasibility certificate for this sign convention. Indeed, any feasible $x\ge 0$ would give $b^{\mathsf{T}}q=x^{\mathsf{T}}{A}^{\mathsf{T}}q\ge 0$.

Use the standard-form problem of Revised simplex standard-form linear program. Assume $A$ has full row rank $m$. An ordered basis is a list $B=(B_1,\dots ,B_m)$ of distinct column indices for which the square matrix $A_B=[a_{B_1}\cdots a_{B_m}]$ is invertible. Write $N=\{1,\dots ,n\}\setminus \{B_1,\dots ,B_m\}$ and $c_B=(c_{B_1},\dots ,c_{B_m}{)}^{\mathsf{T}}$. The basic vector $x(B)$ is defined by $x_B(B)=A_B^{-1}b$ and $x_j(B)=0$ for $j\in N$; the basis is primal feasible, and $x(B)$ is a basic feasible solution, exactly when $A_B^{-1}b\ge 0$.

The basis multiplier is $y(B)=A_B^{-\mathsf{T}}{c}_B$. For every column $j$, its reduced cost is ${\bar{c}}_j=c_j-a_j^{\mathsf{T}}y(B)$. In particular, ${\bar{c}}_{B_i}=0$ for each basic index. The basis is dual feasible when ${\bar{c}}_j\ge 0$ for every $j\in N$. When $m=0$, take the empty basis and the empty multiplier; these formulas remain meaningful.

A primal-feasible basis is degenerate if some basic coordinate is zero. A simplex pivot is degenerate if its ratio-test step length is zero.

Input a standard-form problem as in Revised simplex standard-form linear program, whose stored matrix, right-hand side, and cost entries are finite binary floating-point values, together with finite stored candidate vectors $\widehat{x}\in {\mathbb{R}}^n$ and $\widehat{y}\in {\mathbb{R}}^m$. A finite binary value is interpreted as its exact dyadic rational (an integer times an integer power of $2$). If a dimension is wrong or any value is NaN or infinite, return invalid-input. Otherwise use exact integer/rational arithmetic to compute $r_p=A\widehat{x}-b$, $r_d=c-A^{\mathsf{T}}\widehat{y}$, $g=c^{\mathsf{T}}\widehat{x}-b^{\mathsf{T}}\widehat{y}$, ${\rho }_p=\mathrm{\parallel }{r}_p{\mathrm{\parallel }}_{\mathrm{\infty }}$, and ${\rho }_d=\mathrm{\parallel }{r}_d{\mathrm{\parallel }}_{\mathrm{\infty }}$, where $\mathrm{\parallel }z{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_i\mathrm{\mid }{z}_i\mathrm{\mid }$ and the empty-vector value is zero. Return these exact values and $\mathrm{\mid }g\mathrm{\mid }$ as the exact primal-dual objective difference for the stored data. Return verified-optimal-for-stored-data exactly when $\widehat{x}\ge 0$, $r_p=0$, $r_d\ge 0$, and $g=0$. In every other finite-input case return candidate-only with the residuals and gap; a nonzero or small residual is never rounded to zero and does not certify infeasibility.

The exact arithmetic is a verification procedure for a candidate produced by a floating-point solver; it does not define a basis factorization or bound uncertainty in data before they were stored. If a statement about pre-rounded data is required, separate certified input intervals must be supplied and propagated. The procedure makes no operation-count or runtime claim.

Let $A\in {\mathbb{R}}^{m\times n}$ have full row rank and let $P(A,b)$ be the feasible set of Revised simplex standard-form linear program. For a feasible $x$, define its support by $S(x)=\{j:x_j>0\}$. A set $C$ is convex if $tu+(1-t)v\in C$ for all $u,v\in C$ and $0<t<1$. A point $x\in C$ is an extreme point if every representation $x=tu+(1-t)v$ with $u,v\in C$ and $0<t<1$ forces $u=v=x$. Then $x$ is an extreme point of $P(A,b)$ if and only if the columns $\{a_j:j\in S(x)\}$ are linearly independent. This is equivalent to $x$ being a basic feasible solution for Basis dictionaries and reduced costs for revised simplex. In particular, every nonempty $P(A,b)$ has a basic feasible solution. The statement includes $m=0$ using the empty-basis convention.

Let $B$ be a primal-feasible basis for the standard-form problem of Revised simplex standard-form linear program and Basis dictionaries and reduced costs for revised simplex, and let $j$ be a nonbasic index with reduced cost ${\bar{c}}_j<0$. Put $d=A_B^{-1}{a}_j$. If $d_i\le 0$ for every basic row $i$, then $r_j=1$, $r_B=-d$, and $r_k=0$ for the other nonbasic indices define a feasible ray with $Ar=0$ and $c^{\mathsf{T}}r={\bar{c}}_j<0$; the LP is unbounded below. If some $d_i>0$, the step $\theta ={\min }_{d_i>0}(x_{B_i}\mathrm{/}{d}_i)$ is finite and nonnegative, every minimizing row gives a valid pivot, the new basic vector is feasible, and the objective change is $\theta {\bar{c}}_j\le 0$, strictly negative exactly when $\theta >0$. Finally, if all nonbasic reduced costs are nonnegative at a primal-feasible basis, its basic vector is optimal.

Input the exact standard-form data of Revised simplex standard-form linear program with full-row-rank $A$ and a primal-feasible basis $B$ as in Basis dictionaries and reduced costs for revised simplex. Use exact arithmetic. At each iteration compute $x_B=A_B^{-1}b$, $y=A_B^{-\mathsf{T}}{c}_B$, and all nonbasic reduced costs ${\bar{c}}_j=c_j-a_j^{\mathsf{T}}y$.

1. If every nonbasic ${\bar{c}}_j\ge 0$, return optimal with $x(B)$ and $y$.
2. Otherwise choose the least index $j\mathrm{\notin }B$ with ${\bar{c}}_j<0$ and solve $A_{B}d=a_j$.
3. If no component $d_i$ is positive, return unbounded with the ray whose $j$th component is $1$, whose basic components are $-d$, and whose other nonbasic components are $0$.
4. Otherwise compute $\theta ={\min }_{d_i>0}{x}_{B_i}\mathrm{/}{d}_i$. Among minimizing rows, leave the basic variable of least index. Replace its basis column by $a_j$ and repeat.

The algorithm assumes an exact initial feasible basis. It makes no iteration bound polynomial in $m$ or $n$.

Input the exact standard-form data and a basis $B$ for which every nonbasic reduced cost is nonnegative, as in Revised simplex standard-form linear program and Basis dictionaries and reduced costs for revised simplex. Also input a nonnegative integer pivot budget $K$. Set $k=0$ and repeat:

1. Compute $x_B=A_B^{-1}b$ and $y=A_B^{-\mathsf{T}}{c}_B$. If $x_B\ge 0$, return optimal with the primal basic vector and $y$.
2. Otherwise choose the least-index basic variable $B_i$ with $x_{B_i}<0$. For each nonbasic $j$ compute $d_{ij}=(A_B^{-1}{a}_j{)}_i$. If no $d_{ij}<0$, return infeasible with $q=A_B^{-\mathsf{T}}{e}_i$.
3. If $k=K$, return pivot-budget-exhausted with the current basis and multiplier $y=A_B^{-\mathsf{T}}{c}_B$.
4. Among $j$ with $d_{ij}<0$, choose one minimizing ${\bar{c}}_j\mathrm{/}(-d_{ij})$, with least variable index among ties. Replace $B_i$ by $j$, set $k\leftarrow k+1$, and repeat.

The pivot-budget-exhausted status is inconclusive. No finite-success or anti-cycling claim is part of this definition.

Let $A\in {\mathbb{R}}^{m\times n}$ be represented by a valid CSR record with row pointers $r$, column indices $c_t$, values $v_t$, and $s$ stored entries, under Compressed sparse row matrices with stored-entry semantics. Matrix and vector coordinates here are zero-based: row $i$ and column $j$ correspond to row $i+1$ and column $j+1$ in Basis dictionaries and reduced costs for revised simplex, with the same relabelling for $y,c,w$ and basis-column indices. For each $0\le t<s$, let $i(t)$ be the unique row satisfying $r_{i(t)}\le t<r_{i(t)+1}$. For a cost vector $c\in {\mathbb{R}}^n$ and given $y\in {\mathbb{R}}^m$, initialize $w\in {\mathbb{R}}^n$ to zero and, for $t=0,\dots ,s-1$, update $w_{c_t}\leftarrow w_{c_t}+v_t{y}_{i(t)}\mathrm{.}$ In exact real arithmetic the resulting vector is $A^{\mathsf{T}}y$. This loop uses exactly $s$ multiplications and $s$ additions, preceded by $n$ zero initializations; forming $c-w$ uses $n$ subtractions and gives the reduced-cost vector of Basis dictionaries and reduced costs for revised simplex under the stated relabelling when $y=y(B)$. Every stored entry is counted, including repeated column indices and explicitly stored zeros. The claim is an arithmetic-operation count; it gives no runtime, bandwidth, or factorization bound.

For a real standard-form problem with $A\in {\mathbb{R}}^{m\times n}$ and candidate vectors $x\in {\mathbb{R}}^n$, $y\in {\mathbb{R}}^m$, define $r_p=Ax-b$, $r_d=c-A^{\mathsf{T}}y$, and $g=c^{\mathsf{T}}x-b^{\mathsf{T}}y$. When the data and candidates are finite stored binary floating-point values, Exact residual audit of finite-precision simplex candidates computes precisely these quantities, interpreting the stored values as exact dyadic rationals. For all the stated real data, $g=x^{\mathsf{T}}{r}_d+y^{\mathsf{T}}{r}_p,$ and consequently $\mathrm{\mid }g\mathrm{\mid }\le \mathrm{\parallel }x{\mathrm{\parallel }}_1\mathrm{\parallel }{r}_d{\mathrm{\parallel }}_{\mathrm{\infty }}+\mathrm{\parallel }y{\mathrm{\parallel }}_1\mathrm{\parallel }{r}_p{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{.}$ Here $\mathrm{\parallel }z{\mathrm{\parallel }}_1={\sum }_i\mathrm{\mid }{z}_i\mathrm{\mid }$ and $\mathrm{\parallel }z{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_i\mathrm{\mid }{z}_i\mathrm{\mid }$, with both norms equal to zero on the empty vector. This bounds the primal-dual objective difference; when either vector is infeasible it does not bound distance to an optimal value. If $Ax=b$, $x\ge 0$, $c-A^{\mathsf{T}}y\ge 0$, and $g=0$, then $x$ is optimal.

For exact arithmetic and a finite standard-form LP with full-row-rank $A$, the primal algorithm of Primal revised simplex with Bland's rule, started from any primal-feasible basis, terminates after finitely many pivots at an optimal basis or returns a feasible ray of strictly negative cost. If the feasible set is nonempty and the objective is bounded below, an optimal basis exists and is returned. The number of pivots is at most the number of possible bases, hence at most $\left(\genfrac{}{}{0px}{}{n}{m}\right)$; this is a finiteness bound, not a polynomial-time claim. Every pivot may be degenerate, so the objective need not decrease strictly at each step.

Let $B$ be a basis of the minimization problem for which all nonbasic reduced costs are nonnegative. At an iteration of Dual revised simplex with a finite pivot budget, a pivot chosen from a row $i$ with $x_{B_i}<0$ and a column $j$ with $d_{ij}=(A_B^{-1}{a}_j{)}_i<0$ minimizing ${\bar{c}}_j\mathrm{/}(-d_{ij})$ preserves dual feasibility. If there is no nonbasic $j$ with $d_{ij}<0$, then $q=A_B^{-\mathsf{T}}{e}_i$ satisfies $A^{\mathsf{T}}q\ge 0$ and $b^{\mathsf{T}}q<0$, so $q$ is a Farkas infeasibility certificate as defined in Revised simplex standard-form linear program and the primal problem is infeasible. If the current basis is both primal and dual feasible, it is optimal. A finite pivot-budget exhaustion is inconclusive and does not assert infeasibility or convergence.

Input any exact equality system $Ax=b$ with $x\ge 0$, including a rank-deficient raw system. Let $D$ be diagonal with $D_{ii}=-1$ when $b_i<0$ and $D_{ii}=1$ otherwise; set $\tilde{A}=DA$ and $\tilde{b}=Db\ge 0$. Add artificial variables $u\in {\mathbb{R}}^m$ and solve the Phase I problem $\min {\mathbf{1}}^{\mathsf{T}}u$ subject to $\tilde{A}x+u=\tilde{b}$, $x,u\ge 0$, starting at $x=0,u=\tilde{b}$ with artificial basis $I_m$. Use the exact primal algorithm of Primal revised simplex with Bland's rule and its finite-termination result Bland-rule finite termination and optimal-basis existence.

At a terminal optimum, if ${\mathbf{1}}^{\mathsf{T}}u>0$, return infeasible and the basis multiplier $y$ for the Phase I objective. If the optimum is zero, set every artificial variable to zero and remove artificial basic variables as follows. For a zero-valued artificial basic variable, inspect its row in $B^{-1}\tilde{A}$. If some original nonbasic column has a nonzero coefficient there, pivot the least-index such column into the basis; the pivot may have either sign because the leaving basic value is zero. If no such coefficient exists, and the transformed right-hand-side entry is zero, delete that redundant equation and its zero artificial basic variable. Repeat until all remaining basic columns are original; return the row-reduced equivalent system and its original feasible basis. A zero row with nonzero transformed right-hand side returns inconsistent-row. All tests are exact; a finite-precision near-zero objective is not treated as zero.

For any exact system $Ax=b$, $x\ge 0$, the Phase I procedure of Phase I revised simplex and rank reduction terminates. Its minimum artificial-variable sum is zero if and only if the original system is feasible. If the minimum is positive, its returned vector yields a Farkas infeasibility certificate, as defined in Revised simplex standard-form linear program, with $A^{\mathsf{T}}q\ge 0$ and $b^{\mathsf{T}}q<0$. If the minimum is zero, the extraction procedure returns an equivalent full-row-rank reduced system with a basic feasible solution using only original columns; zero-valued artificial basic variables are either pivoted out or their redundant equations are removed.

Input finite stored binary data for the standard-form LP of Basis dictionaries and reduced costs for revised simplex, with full-row-rank $A\in {\mathbb{R}}^{m\times n}$, a candidate ordered basis $B$ of $m$ distinct in-range indices, and a nonnegative integer budget $K$ of basis evaluations. Stored values represent their exact dyadic rationals. Invalid dimensions, nonfinite inputs or repeated/out-of-range basis indices return invalid-input. Nonsingularity of $C=A_B$ must be established as part of an admitted basis input; a numerical rank threshold is not such an establishment. A basis whose validity is unavailable returns basis-validity-inconclusive.

A caller may request a primal or dual simplex transition after an audit, or only an audit. It may supply a finite sequence of transition records, one for each requested basis replacement, from Primal revised simplex with Bland's rule or Dual revised simplex with a finite pivot budget. A transition record has fields mode (primal or dual), basis_before (the ordered current basis, with its validity witness), leaving_position $i$, and entering_index $j$; it is checked rather than trusted as already verified. The initial basis and each record's basis_before must carry the validity witness described here. After a replacement, its checked nonzero pivot coefficient establishes the new basis; any next transition record must carry its own checked validity witness.

An admitted basis input includes either an exact rational inverse witness $G$ with $CG=GC=I_m$, checked exactly, or a rational matrix $H$ and rational $q$ with $0\le q<1$ and $\mathrm{\parallel }{I}_m-HC{\mathrm{\parallel }}_{\mathrm{\infty }}\le q$, also checked exactly. For matrices with at least one row, $\mathrm{\parallel }M{\mathrm{\parallel }}_{\mathrm{\infty }}={\max }_i{\sum }_j\mathrm{\mid }{M}_{ij}\mathrm{\mid }$; the empty matrix has norm $0$. For vectors it is the maximum absolute coordinate, with empty value $0$. For $m=0$, the empty inverse witness satisfies the identities. If neither validity certificate is verified, return basis-validity-inconclusive before factorization. A numerical rank threshold is never a validity certificate.

With an exact inverse witness, first compare basis_before with the current ordered basis exactly. Then check a transition by exact rational arithmetic: compute $x_B=Gb$, $y=G^{\mathsf{T}}{c}_B$, $d_k=G{a}_k$ for every nonbasic $k$, and ${\bar{c}}_k=c_k-a_k^{\mathsf{T}}y$. A primal record is admissible exactly when $x_B\ge 0$, $j$ is the least-index nonbasic column with ${\bar{c}}_j<0$, some $d_{rj}>0$, and $i$ minimizes $x_{B_r}\mathrm{/}{d}_{rj}$ over rows with $d_{rj}>0$, with ties resolved by least basic-variable index. A dual record is admissible exactly when every nonbasic ${\bar{c}}_k\ge 0$, $B_i$ is the least-index basic variable with $x_{B_i}<0$, $d_{ij}<0$, and $j$ minimizes ${\bar{c}}_k\mathrm{/}(-d_{ik})$ over nonbasic $k$ with $d_{ik}<0$, with ties resolved by least variable index. In either case, the checked nonzero pivot coefficient proves the replacement basis nonsingular.

Certified rational enclosures may instead establish a transition. For each current $D=C$ and $D=C^{\mathsf{T}}$, provide rational $H_D,q_D,M_D$ with $0\le q_D<1$, $\mathrm{\parallel }{I}_m-H_{D}D{\mathrm{\parallel }}_{\mathrm{\infty }}\le q_D$, and $M_D\ge \mathrm{\parallel }{H}_D{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}(1-q_D)$; verify these inequalities exactly. For each solve $Dz=r$, combine its returned candidate $\widehat{z}$ and a rational upper bound $\eta$ for its Step 3 residual bound to form the coordinate intervals $[{\widehat{z}}_{\mathrm{\ell }}-M_D\eta ,{\widehat{z}}_{\mathrm{\ell }}+M_D\eta ]$. For closed rational intervals $I=[a,b]$ and $J=[c,d]$, use $I+J=[a+c,b+d]$, $I-J=[a-d,b-c]$, $IJ=[\min \{ac,ad,bc,bd\},\max \{ac,ad,bc,bd\}]$, and $I\mathrm{/}J=I\cdot [\min \{1\mathrm{/}c,1\mathrm{/}d\},\max \{1\mathrm{/}c,1\mathrm{/}d\}]$ when $0\mathrm{\notin }J$; division is undefined otherwise. Evaluate dot products, reduced costs, and ratio expressions with these exact rational endpoint operations. First compare basis_before with the current ordered basis exactly. An interval proves a sign or order only when its endpoints imply that relation. If a ratio comparison is not decided by interval endpoints, return pivot-inconclusive unless an exact inverse witness $G$ is supplied for the current basis; with $G$, compute the exact rational ratios and compare them exactly, resolving equality by the least-index rule. Admit the record only when the required signs and comparisons, including all least-index rules, are proved. If a needed sign, ratio comparison, or basis match is not established, return pivot-inconclusive with the current basis and its last completed audit, without changing the basis.

For $m\ge 1$, use the operationwise arithmetic of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add, with $0<u<1$, $mu<1$, $(m+3)u<1$, and ${\gamma }_{m+3}<1\mathrm{/}8$. All nonzero exact intermediates must be normal. Norms and certificate expressions below are evaluated exactly or by certified upward bounds; failure to obtain a finite valid bound is a numerical failure. Process the following loop:

1. Maintain an attempt counter $t$, initially $0$. If $t=K$, return budget-exhausted with the current basis, the last completed audit if any, and the basis to which that audit belongs. Otherwise set $t\leftarrow t+1$ before starting this basis evaluation. Every budget, numerical-failure, basis-validity-inconclusive, or pivot-inconclusive return includes the current basis and identifies the basis associated with any retained audit; state explicitly when no audit exists.

2. Separately for $D=C=A_B$ and $D=C^{\mathsf{T}}$, copy the current stored entries into a working matrix $W$. For $k=1,\dots ,m$, set $r=m-k+1$, take the active column $x=W_{k:m,k}$ and trailing block $T=W_{k:m,k+1:m}$, and call Scaled Householder reflector formation and application once on $(x,T)$. On success, save its reflector data and replace the active block $W_{k:m,k:m}$ by its returned output, which writes the new diagonal entry and exact zeros below it; leave earlier rows and columns unchanged. If $x=0$, save an identity marker and leave the trailing block unchanged. Stop with numerical-failure at the first failed call, recording the factorization, column $k$, and failure stage. The final $W$ is the computed upper-triangular factor ${\widehat{R}}_D$.

   To apply these stored reflectors to any right-hand side $s$, start with $z=s$ and visit $k=1,\dots ,m$ in that same order. Skip an identity marker. Otherwise, on the active suffix $z_{k:m}$ compute the sequential rounded dot $d=\mathrm{fl}(v_k^{\mathsf{T}}{z}_{k:m})$, then $p=\mathrm{fl}({\widehat{\tau }}_k{v}_k)$, $u=\mathrm{fl}(pd)$ componentwise, and $z_{k:m}=\mathrm{fl}(z_{k:m}-u)$ componentwise, using the operation order of Scaled Householder reflector formation and application without a column overwrite. Stop at the first failure and record the right-hand side, reflector index, and failure stage. For $Dz=s$, apply this replay to obtain the transformed right-hand side and solve ${\widehat{R}}_D\widehat{z}=z$ by descending substitution: for $i=m,\dots ,1$, sequentially compute $t_i=\mathrm{fl}({\sum }_{j=i+1}^m({\widehat{R}}_D{)}_{ij}{\widehat{z}}_j)$, $h_i=\mathrm{fl}(z_i-t_i)$, and ${\widehat{z}}_i=\mathrm{fl}(h_i\mathrm{/}({\widehat{R}}_D{)}_{ii})$. A zero diagonal or any failed operation returns numerical-failure with the solve and row index. Reuse the $C$ factorization for ${\widehat{x}}_B$ and every nonbasic direction ${\widehat{d}}_j$; reuse the $C^{\mathsf{T}}$ factorization for $\widehat{y}$. Never substitute a rounded dense orthogonal product for the exact orthogonal representative in the proof. After every admitted basis replacement discard both factorizations and recompute; no rank-one factorization-update implementation is claimed.

3. Independently certify each returned solve for its actual current matrix $D=C$ or $C^{\mathsf{T}}$ and right-hand side $r$. Compute $\widehat{v}=\mathrm{fl}(D\widehat{z})$ and $\widehat{w}=\mathrm{fl}(\widehat{v}-r)$ by the sequential products/subtraction of Rounded matrix products give certified linear and normal-equation residual allowances. Put $g_m=\frac{1+6u}{1-(m-1)u}-1,W=g_m\mathrm{\parallel }D{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}_2+u(\mathrm{\parallel }\widehat{v}{\mathrm{\parallel }}_2+\mathrm{\parallel }r{\mathrm{\parallel }}_2)\mathrm{.}$ With the local coefficient ${\kappa }_m$ of The scaled computed Householder step satisfies the local backward error premise, put $\beta =(1+{\kappa }_m{)}^m-1,{\beta }_D=\beta +{\gamma }_{m+3}(1+\beta ),$ and report the valid upper bound $\eta (D,r,\widehat{z})=\min \{\mathrm{\parallel }\widehat{w}{\mathrm{\parallel }}_2+W,{\beta }_D\mathrm{\parallel }D{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}_2+\beta \mathrm{\parallel }r{\mathrm{\parallel }}_2\}\mathrm{.}$ A finite concrete certificate option uses exact rational arithmetic on the stored dyadic entries and a rational upper bound for $u$ satisfying all displayed admissibility inequalities. Use $\mathrm{\parallel }v{\mathrm{\parallel }}_2\le {\sum }_i\mathrm{\mid }{v}_i\mathrm{\mid }$ and $\mathrm{\parallel }D{\mathrm{\parallel }}_F\le {\sum }_{i,j}\mathrm{\mid }{D}_{ij}\mathrm{\mid }$ as rational upper bounds for every norm in the two nonnegative expressions. For the local coefficient, substitute ${\bar{e}}_m=(1+u{)}^{m+3}-1$ for $e_m=(1+u{)}^{m\mathrm{/}2+3}-1$ in the source formula: put ${\bar{d}}_m={\bar{e}}_m+u(2+{\bar{e}}_m)$, $a_m=(1+u)\mathrm{/}(1-u{)}^m-1$, $g_m^{\mathrm{Q}\mathrm{R}}=mu\mathrm{/}(1-mu)$, $c_m=2((1+a_m)(1+u{)}^2(1+g_m^{\mathrm{Q}\mathrm{R}})-1)$, and ${\bar{\kappa }}_m=\max \{{\bar{e}}_m+8{\bar{d}}_m,(1+u)c_m+3u\}$. These are rational upper bounds because $m+3\ge m\mathrm{/}2+3$ and all constituent nonnegative formulas increase in their arguments. Then $\bar{\beta }=(1+{\bar{\kappa }}_m{)}^m-1$ and ${\bar{\beta }}_D=\bar{\beta }+{\gamma }_{m+3}(1+\bar{\beta })$ are rational upper bounds for the QR coefficients. Compute both candidate bounds by finite exact rational sums/products/powers and take their minimum as the returned $\eta$. This implements the certificate without a norm oracle; other finite certified upper-bound procedures are allowed. Any factorization, substitution, dot, subtraction, range or certificate failure returns numerical-failure, with its stage and the last completed audit; it returns no certificate for the failed solve.

4. Embed ${\widehat{x}}_B$ in $\widehat{x}\in {\mathbb{R}}^n$ with zero nonbasic entries, and call Exact residual audit of finite-precision simplex candidates on these actual stored $\widehat{x},\widehat{y}$. Retain its exact $r_p=A\widehat{x}-b$, $r_d=c-A^{\mathsf{T}}\widehat{y}$, objective difference $g$, and audit status together with all solve residual bounds. basis-solves-residual-certified means only that the returned bounds certify those linear equations; any requested thresholds must also be checked before declaring them met. verified-optimal-for-stored-data is issued only by the exact audit's primal/sign/zero-gap checks. Other completed candidates remain candidate-only; small residuals or a failed/ambiguous pivot never certify infeasibility.

5. Return if audit-only mode or the caller has no further transition. Otherwise compare the next record with the current basis and apply the exact or enclosure admission predicate above. A failed or unresolved predicate returns pivot-inconclusive or basis-validity-inconclusive, retaining the current basis and last completed audit. On admission, replace position $i$ by $j$, discard both factorizations, and continue at Step 1. Exact driver invariants remain those of the existing driver, not consequences of successful floating solves.