Bounded strict dominance
After constructing a workspace, dominance is the inference step that may reduce the solver input. This page explains which signs justify a fixing and how to resume a bounded pass. See the solve walkthrough for what to do with its residual and report.
Select Workspace(model; rules=:dominance) and call propagate! explicitly, or use preprocess(model; rules=:dominance, limits...). For queue-driven degree-0/1/2 exact local elimination (including arbitrary local fields, fill-edge merging/cancellation and optional alternating dominance/elimination cascades), select Workspace(model; rules=:elimination) or call eliminate_low_degree!(ws; cascade_dominance=true, ...). For queue-driven certified pair relations and reversible signed contractions (:interval, :exact, Glover–Lewis–Kochenberger cross-endpoint :glk_pair, and shared-neighborhood co-flip / twin contraction :coflip_pair), select Workspace(model; rules=:relations) or call contract_relations!(ws; max_fill=..., cascade_dominance=..., ...) and inspect active representatives/parities via relation_map(ws). For deterministic mixed pass scheduling across all four reduction families on one shared Workspace and Generation without alternating QUBO↔Ising materializations, select Workspace(model; rules=:mixed) or preprocess(model; rules=:mixed, ...) and call schedule_reductions!(ws; ...). Identity remains the default. Neither path dispatches a solver or implicitly materializes a residual. In pure dominance mode (propagate!(ws)), only strong unary dominance is enabled: every reported value holds in all optima within the current caller scope. Local variable elimination (eliminate_variable!, eliminate_low_degree!) records an EliminationStep in reductions(ws) with its conditional argmin reconstruction table rather than reporting the variable in deductions(ws) as a globally fixed constant; when boundary ties occur (tie_break=:low or :high), persistency(step) is :weak and preserves the optimal objective value and at least one optimal reconstruction without claiming that all original optima or their multiplicities are represented by a single tie choice. Pair relations, weak ties, roof duality and heuristic choices are separate methods.
For minimization of the normalized objective, a binary derivative has bounds aᵢ + Σ min(0,bᵢⱼ) and aᵢ + Σ max(0,bᵢⱼ) over free neighbors. A strictly positive lower bound fixes 0; a strictly negative upper bound fixes 1. For spins the field bounds are aᵢ ± Σ abs(bᵢⱼ), fixing -1/+1 respectively. The boundary field includes fixed neighbors. Maximization and negative scale reverse the sign; positive scale magnitude does not alter optima. Zero scale and equality yield no fixing. The binary/spin rules are equivalent under x=(s+1)/2, rather than independent strengthening methods.
Certified pair relations and Glover–Lewis–Kochenberger rules
For two free variables $u \ne v$ and candidate parity $\sigma \in \{-1, +1\}$ (representing $t_u = \sigma t_v$ in normalized gauged spin coordinates, or $x_u = x_v$ for $\sigma_{\text{orig}} = +1$ and $x_u = 1 - x_v$ for $\sigma_{\text{orig}} = -1$ in binary coordinates), the two violating spin configurations are $V_1 = (t_u = -\sigma, t_v = +1)$ and $V_2 = (t_u = +\sigma, t_v = -1)$. Let $\tilde{h}_i$ and $\tilde{J}_{ij}$ denote the direction-normalized spin fields and couplings, and let $R_u = \sum_{w \notin \{u, v\}} |\tilde{J}_{uw}|$ and $R_v = \sum_{w \notin \{u, v\}} |\tilde{J}_{vw}|$.
- Single-endpoint coupling dominance (
:interval,:exact): generalizes Boettcher–Davidheiser (2020) Section II Rule VI to arbitrary local fields by requiring flips of $t_u$ alone to improve both $V_1$ and $V_2$: $-\sigma \tilde{J}_{uv} - |\tilde{h}_u| - R_u > 0$ (:strong) or $\ge 0$ (:weakwithallow_weak=true). - Glover–Lewis–Kochenberger (2018) Section 3 Theorems 3.1–3.4 cross-endpoint pair rule (
:glk_pair): translated from GLK's maximization of $\sum_i c_i x_i + \sum_{i \ne j} Q_{ij} x_i x_j$ (with symmetric off-diagonal $Q_{ij} = Q_{ji} = q_{ij}/2$) to normalized minimization in spin coordinates, and requiring a favoring coupling $\text{center} = -\sigma \tilde{J}_{uv} > 0$:- Branch A rules out $V_1$ by flipping $t_u \to +\sigma$ (half-margin $m_u(V_1) = -\sigma \tilde{J}_{uv} - \sigma \tilde{h}_u - R_u$) and $V_2$ by flipping $t_v \to +1$ (half-margin $m_v(V_2) = -\sigma \tilde{J}_{uv} - \tilde{h}_v - R_v$), mapping both violating states directly to $(+\sigma, +1)$ in one flip.
- Branch B rules out $V_1$ by flipping $t_v \to -1$ (half-margin $m_v(V_1) = -\sigma \tilde{J}_{uv} + \tilde{h}_v - R_v$) and $V_2$ by flipping $t_u \to -\sigma$ (half-margin $m_u(V_2) = -\sigma \tilde{J}_{uv} + \sigma \tilde{h}_u - R_u$), mapping both violating states directly to $(-\sigma, -1)$ in one flip.
:strongpersistency and $\text{lo}_{\text{glk}} == 0$ (whenallow_weak=trueand $\text{center} > 0$) certifies:weakpersistency. - Shared-neighborhood co-flip pair dominance and twin/clique contraction (
:coflip_pair, Ferizovic et al. 2020; Rehfeldt et al. 2023): on any violating state $t_u = -\sigma t_v$, flipping $t_u \to \sigma t_v$ or $t_v \to \sigma t_u$ yields half-energy gains $m_u(s)$ and $m_v(s)$ whose average cancels every matched external coupling $\tilde{J}_{uw} = \sigma \tilde{J}_{vw}$:\[\frac{m_u(s) + m_v(s)}{2} = -\sigma \tilde{J}_{uv} - \frac{t_v}{2}\!\left((\tilde{h}_u - \sigma \tilde{h}_v) + \sum_{w \notin \{u, v\}} (\tilde{J}_{uw} - \sigma \tilde{J}_{vw}) t_w\right) \ge -\sigma \tilde{J}_{uv} - \operatorname{rad}_{\text{coflip}}(\sigma) = L_{\text{coflip}}(\sigma),\]
where $\operatorname{rad}_{\text{coflip}}(\sigma) = \frac{1}{2}|\tilde{h}_u - \sigma \tilde{h}_v| + \frac{1}{2}\sum_{w \notin \{u, v\}} |\tilde{J}_{uw} - \sigma \tilde{J}_{vw}|$. Hence $\max(m_u(s), m_v(s)) \ge L_{\text{coflip}}(\sigma)$ on every boundary assignment: $L_{\text{coflip}}(\sigma) > 0$ certifies:strongpersistency (including adjacent twins and uniform cliques where $R_u, R_v > |\tilde{J}_{uv}|$ and $\tilde{h}_u = \tilde{h}_v = 0$ block both Rule 1 and:glk_pair), while $L_{\text{coflip}}(\sigma) == 0$ withallow_weak=truecertifies:weakpersistency (including non-adjacent exact signed twins $\tilde{J}_{uv} = 0$, $\operatorname{rad}_{\text{coflip}}(\sigma) = 0$, discovered automatically via shared 2-hop neighbors with zero fill edges). - Explicitly deferred GLK rules: single-branch inequality implications ($x_u + x_v \ge 1$, $x_u + x_v \le 1$, $x_u \le x_v$ when only one of $V_1, V_2$ is ruled out) do not induce an unconstrained parity substitution $s_u = \pm s_v$ without auxiliary slack variables or penalty terms, and GLK Section 4 multi-neighbor matrix rules require higher-order neighborhood scans; both are explicitly deferred outside unconstrained quadratic pair contraction.
Guarded zero-field degree-3 Ising star–triangle reduction
Eliminating a degree-three vertex $s_u \in \{-1, +1\}$ with neighbors $s_1, s_2, s_3 \in \{-1, +1\}$ generally introduces a cubic term $J_{123} s_1 s_2 s_3$. When the current effective Ising field of the center is rigorously zero ($h_u = 0$), spin-flip symmetry implies that the local optimal contribution (for minimization with positive scale, $\operatorname{dir} = +1$; negated when $\operatorname{dir} = -1$),
\[\phi(s_1, s_2, s_3) = -\operatorname{dir} \cdot |J_1 s_1 + J_2 s_2 + J_3 s_3|,\]
is an even function $\phi(-s_1, -s_2, -s_3) = \phi(s_1, s_2, s_3)$ of the three neighbors. Consequently, both its linear Fourier terms and its cubic Fourier term vanish identically, yielding the pure constant + pairwise triangle representation of Boettcher–Davidheiser (2008), Section II Rule V Eq. (4) (translated from the paper's leading-minus Hamiltonian $H = -\sum J_{ij} \sigma_i \sigma_j$ to this package's $\min_s (s^T J s + h^T s + c)$ convention):
\[\begin{aligned} \varepsilon_0 &= |J_1 + J_2 + J_3|, \quad \varepsilon_1 = |-J_1 + J_2 + J_3|, \quad \varepsilon_2 = |J_1 - J_2 + J_3|, \quad \varepsilon_3 = |J_1 + J_2 - J_3|, \\ \Delta c_{\text{spin}} &= -\operatorname{dir} \cdot \frac{\varepsilon_0 + \varepsilon_1 + \varepsilon_2 + \varepsilon_3}{4}, \\ \Delta J_{12} &= -\operatorname{dir} \cdot \frac{\varepsilon_0 - \varepsilon_1 - \varepsilon_2 + \varepsilon_3}{4}, \quad \Delta J_{13} = -\operatorname{dir} \cdot \frac{\varepsilon_0 - \varepsilon_1 + \varepsilon_2 - \varepsilon_3}{4}, \quad \Delta J_{23} = -\operatorname{dir} \cdot \frac{\varepsilon_0 + \varepsilon_1 - \varepsilon_2 - \varepsilon_3}{4}. \end{aligned}\]
Neighbor fields $h_1, h_2, h_3$ may be arbitrary (spin_field_deltas on $w_1, w_2, w_3$ are zero when $h_u = 0$). More generally, when $h_u \ne 0$, the conditional minimum $\phi(s_1, s_2, s_3) = \min_{s_u \in \{\pm 1\}} s_u(h_u + \sum_{k=1}^3 J_k s_k)$ has vanishing 3-way Walsh–Fourier / Möbius cubic coefficient ($\alpha_{123} = 0$, so $\phi$ is an exact quadratic polynomial over $\{\pm 1\}^3$) if and only if one of three trichotomy conditions holds:
- $h_u = 0$ (zero-field star–triangle reduction, Eq. 4);
- $|h_u| \ge |J_1| + |J_2| + |J_3|$ (unary coercive-field dominance, introducing 0 fill edges); or
- $2 \max_{k \in \{1,2,3\}} |J_k| \ge |h_u| + |J_1| + |J_2| + |J_3|$ (heavy-edge relation dominance, introducing at most 2 fill edges incident to the dominant neighbor $w_{k^*}$ and 0 fill edges between the two non-dominant neighbors).
All three $\alpha_{123} = 0$ regimes are certified and verified by prove_elimination, eliminate_variable!, and eliminate_low_degree! when max_degree=3, while degree-3 vertices with $\alpha_{123} \ne 0$ are refused with :nonquadratic_elimination (and skipped in $O(1)$ with zero exact table work during eliminate_low_degree!). Conditioning a fourth neighbor can induce a field $h'_u \ne 0$ with $\alpha_{123} \ne 0$ (which invalidates degree-3 eligibility in $O(1)$) or bring $(h'_u, J_1, J_2, J_3)$ into an $\alpha_{123} = 0$ regime (which unlocks degree-3 eligibility). Small floating-point fields are converted to exact Rational{BigInt} without rounding to zero. When max_degree=3 is requested in eliminate_low_degree!, max_fill bounds the number of new triangle edges introduced per step and defers blocked vertices reversibly on the trail so progressive max_fill increases reconsider them without rescanning the graph.
Connected 0-, 1-, and 2-separator block elimination (eliminate_block!, enable_blocks=true)
When a connected subset of active variables $B \subseteq V_{\text{act}}$ with $2 \le |B| \le \text{max\_block\_size} \le 16$ is separated from the rest of the active graph by a boundary $S = N_G(B) \subseteq V_{\text{act}} \setminus B$ of at most two active vertices (0 <= |S| <= max_separator <= 2, Rehfeldt et al. 2023 Section 3), the conditional optimum of the internal block energy over all $2^{|B|}$ internal assignments is a function of at most two binary/spin boundary variables $x_S$:
\[\Phi_B(x_S) = \operatorname{opt}_{x_B \in \mathcal{D}^{|B|}} E_{B,S}(x_B, x_S), \quad x_S \in \mathcal{D}^{|S|}.\]
Because any pseudo-Boolean function of $|S| \le 2$ variables has degree at most 2, $\Phi_B(x_S)$ is always an exact quadratic polynomial on $S$ regardless of internal frustration, internal degree-3+ cubic terms (such as $K_4$ blocks with $\alpha_{123} \ne 0$), or arbitrary local fields:
- 0-separator closed component (
|S| == 0): solved to a pure constant shift $\Delta c = \Phi_B(\emptyset)$ with zero fill edges; - 1-separator articulation-point pendant block (
|S| == 1, $S = \{s_1\}$): eliminated into a constant shift $\Delta c$ and linear shift $\Delta L_{s_1}$ on the articulation vertex $s_1$ with zero fill edges; - 2-separator biconnected block (
|S| == 2, $S = \{s_1, s_2\}$): eliminated into $\Delta c$, linear shifts $(\Delta L_{s_1}, \Delta L_{s_2})$, and a single quadratic coupling shift $\Delta Q_{s_1, s_2}$ between $s_1$ and $s_2$ (introducing at most 1 fill edge when $(s_1, s_2)$ is not already an active edge, subject tomax_fill).
prove_elimination(ws, block_labels; ...) and eliminate_block!(ws, block_labels; ...) certify and commit an atomic batch of |B| EliminationStep records on the reversible trail (the first carrying the polynomial deltas on $S$ and the remaining steps carrying zero deltas and their coordinate's $2^{|S|}$-entry marginal argmin table). Pass enable_blocks=true (along with max_block_size=12, max_separator=2, and require_unique_blocks=false) to eliminate_low_degree! or schedule_reductions! to automatically discover and eliminate 0-, 1-, and 2-separator blocks once single-vertex degree-\le 3 elimination is quiescent.
using QUBOPreprocessing
import QUBOTools as QT
ws = Workspace(QT.Model(Dict(:x=>3.0,:y=>1.0,:isolate=>0.0),
Dict((:x,:y)=>-2.0)); rules=:dominance)
root = checkpoint(ws)
first = propagate!(ws; max_deductions=1)
@assert first.stop_reason == :deduction_limit
@assert verify_certificate(ws,export_certificate(ws)).valid
last = propagate!(ws)
@assert last.stop_reason == :quiescent
@assert isempty(assumptions(ws))
@assert length(deductions(ws)) == 2
result = materialize(ws)
@assert verify_certificate(ws,result.certificate.proof).valid
@assert QT.variables(export_model(result)) == [:isolate]
deductions(ws), last([:x => 0, :y => 0], PropagationReport(Generation(UUID("fb21efa7-03ca-48aa-a5dd-39efa6e89240"), UUID("3c9f82ba-3799-4154-abd4-e6deee914b02")), Checkpoint(Generation(UUID("fb21efa7-03ca-48aa-a5dd-39efa6e89240"), UUID("3c9f82ba-3799-4154-abd4-e6deee914b02")), UUID("34194cd3-f191-442f-95e0-3cee2a3aed0e"), 5, 0x0000000000000005, 2, 0), :quiescent, 2, 1, 1, 6, 0, (candidates = 3, edge_visits = 2, exact_work = 11)))Incremental work and interruption
Construction prepares exact Rational{BigInt} fields and derivative-bound caches once, plus an initial original-index-order queue. Unlike the standalone prove_dominance interval/fallback helper, propagation reads its exact caches and records method=:exact. Installing one deduction updates only its free neighbors and queues each dirty neighbor once. No QUBOTools constructor, full conversion, source copy or proof export occurs per deduction. Bit complexity is additional to structural counts. After the initial scan, an unchanged call performs no candidate or adjacency work. Genuine cascades may touch the graph.
Per-call limits are nonnegative machine-sized integers:
| Limit | Charged work |
|---|---|
max_work | candidate checks plus deduction-update adjacency visits |
max_deductions | committed deductions |
max_exact_work | cached sign checks and conservative reservations of one constant plus three exact values per incident edge for an attempted update |
deadline_ns | absolute UInt64 monotonic time_ns() deadline |
A complete update is reserved before commitment. Fixed-neighbor skips can make exact reservations conservative. If a deduction cannot fit, its queue entry remains pending; its examined candidate/sign check is charged again on resume. Deadline checks surround preparation and run per incident edge; the short commit/queue-journal boundary finishes without interruption. These are algorithmic limits, not hard real-time or asynchronous process-cancellation guarantees.
Reports use :work_limit, :deduction_limit, :verification_limit, :deadline or :quiescent. Every stop retains a sound committed prefix. A later call continues the pending queue. pending includes queued entries already fixed by a cascade until they are consumed. Report totals count executed/reserved propagation work even if the model is later rolled back. Initialization, caller updates, replay, explicit export, verifier and solver costs are separate.
Queue consumption and fixings both have undo records. Rollback restores exact fields, bounds, constant, pending cursor/flags, caller and deduction provenance. changes(ws, cp) returns caller pins; deductions(ws; since=cp) returns only inferences. Both inspect fixing records, skipping queue-only history. Checkpoints are constant-size, and stale branches/resets are rejected. Arbitrary unfix! conservatively discards deductions and replays only retained explicit callers; it is a documented full rebuild. Resume propagation explicitly afterward.
Proof and consumer boundaries
export_certificate(ws) explicitly copies the original source and ordered proof chain, or returns nothing in constant-size work when there are no deductions. Each step records its caller-prefix length: adding a later assumption does not rewrite an earlier bound or constant. The independent verifier substitutes the birth scope and validated predecessor chain in the original polynomial. A root-global step has caller-prefix length zero. Captured certificates require the exact current trail tip; historical branch evidence is rejected after rollback, replay or reset even if the same assignments are reapplied.
materialize captures an owned residual, label map, complete fixed assignment and proof chain. Root deductions have certificate.scope == :original; explicit caller pins produce :assumptions. Caller pins do not prove the branch contains a global optimum of the original problem. Default Float64 export still requires exactly representable residual coefficients/constants; otherwise request coefficient_type=Rational{BigInt} and a compatible consumer. Certified inference does not authorize rounding. Reconstruction validates every free residual value and restores all fixed values in original order. With no free variables, the zero-dimensional residual is handled locally with an empty child state. When free variables remain, propagation does not prove an arbitrary state optimal.
Bounded evidence
The exhaustive tests independently enumerate original/scoped optima on guarded tiny fixtures, compare every residual energy, verify all deductions, and check binary/spin equivalence. Sparse local-change tests compare n=10 and n=2000 work/allocation shape without wall-time thresholds. Run examples/dominance.jl for the resumable cascade and scripts/dominance_pilot.jl for a tiny paired on/off CPU pilot. The pilot charges workspace construction, propagation, proof capture/verification, model export, the same bounded exhaustive child, reconstruction and audit. It retains every paired repetition and separates phases. Reduced variables/edges and total costs are reported together, including no-reduction controls. This pilot is not the accepted operating envelope or an ecosystem adoption decision; those remain with QUBOBenchmarks issue #30.
The retained source artifact docs/evidence/dominance-pilot.md records the producing revision and all paired raw rows. In that tiny warm run, the all-fixed case reduced total time, while the cascade and both no-reduction controls were slower with preprocessing. Variable reduction alone did not predict payoff.
For degree-0/1/2 local elimination (eliminate_low_degree!, examples/elimination.jl, scripts/elimination_pilot.jl, and retained artifact docs/evidence/elimination-pilot.md with raw rows in docs/evidence/elimination-pilot.tsv), the per-degree queues elim_queues[1..4] track only vertices with active degree 0..3 so calls with a smaller max_degree cutoff leave higher-degree buckets untouched for subsequent calls with a larger max_degree without any rescan:
- Dense / high-degree no-benefit control (
dense_k5, 5-vertexK_5):elim_queuesare initially empty (0candidates examined,0edge visits,32 -> 32states). End-to-endon(including workspace construction and residual export) takes1100.78 µs(401.4 KiB) vs650.26 µs(327.5 KiB)off(median paired+431.42 µs). - Tiny sparse instances (
whisker_5, 4-clique core + 1 leaf,n = 5 -> 4): eliminating 1 degree-<= 2vertex halves the exhaustive child search (32 -> 16states), but workspace construction, exactRational{BigInt}table certification, proof verification and residual materialization take481.00 µs(255.2 KiB) vs287.09 µs(257.4 KiB)off(median paired+199.98 µs). - Break-even and sparse payoff (
whisker_7,whisker_10, andcycle_8): each eliminated degree-<= 2vertex halves the downstream exponential search space atO(touched)local cost (<= 4boundary evaluations per vertex), crossing end-to-end break-even against the exact-enumeration child at 3 eliminated variables (whisker_7,128 -> 16states,1824.74 -> 1054.68 µs, median paired−754.36 µs,1274.6 -> 353.7 KiB), reaching a ~14x total time and ~27x allocation reduction at 6 eliminated variables (whisker_10,1024 -> 16states,29738.92 -> 2094.45 µs, median paired−18940.16 µs,13622.6 -> 502.2 KiB), and solvingcycle_8completely where strict dominance removes 0 variables (256 -> 1state,2920.62 -> 1436.53 µs, median paired−1518.64 µs).
For guarded zero-field degree-3 Ising star–triangle reduction (max_degree=3, scripts/star_triangle_pilot.jl, and retained artifact docs/evidence/star-triangle-pilot.md with raw rows in docs/evidence/star-triangle-pilot.tsv), max_degree=2 remains the default policy and max_degree=3 is opt-in:
- Zero-field instances (
zero_field_k4,zero_field_wheel_w6,zero_field_subdivided_10): onzero_field_k4(n = 4),deg3solves the graph completely (16 -> 1state,10/20/37candidate/edge/exact work), but on 16 states the 8-stateRational{BigInt}table certification costs more than direct enumeration (+1707.74 µsvsoff,+667.38 µsvsdeg2). Onzero_field_wheel_w6(n = 6,64 -> 16states,−552.97 µsvsdeg2) andzero_field_subdivided_10(n = 10,1024 -> 256states underdeg2vs1024 -> 32states underdeg3,10192.32 -> 2173.07 µs, median paired−7903.97 µsvsdeg2and−133860.71 µsvsoff), eliminating zero-field degree-3 stars pays off. - Conditioned-field instances (
conditioned_invalidated_8,conditioned_unlocked_8): when a leaf fixing drops a degree-4 hub to degree 3 while inducing a nonzero center field (conditioned_invalidated_8),deg3rejects the hub inO(1)with0additional edge visits and0additional exact table work (12/1/13vs10/1/13); when the induced shift cancels the center field to0(conditioned_unlocked_8),deg3unlocks star–triangle reduction and cascades (128 -> 16states,4635.77 -> 1958.97 µs, median paired−2799.52 µsvsdeg2). - No-benefit nonzero-field control (
no_benefit_cubic_8): on a 3-regular cube where all 8 degree-3 vertices have nonzero fields,deg3rejects all 8 candidates inO(1)with0edge visits and0exact table work (8/0/0work vs0/0/0underdeg2,+926.23 µsvsdeg2).
Mixed exact reduction pass scheduling and 7-phase pipeline accounting
schedule_reductions!(ws; ...) (invoked automatically by preprocess(model; rules=:mixed, ...)) runs a deterministic cheap-first fixpoint loop on one shared Workspace and Generation without alternating QUBO↔Ising model materializations:
- Cheap dirty-neighborhood propagation (
:dominance): drains all dirty unary dominance candidates (st.queue). - Degree-
<= 2local elimination (:elimination): drains buckets 1..3 (degrees 0, 1, 2) undermax_fill/max_total_fill, immediately cascading back to:dominancewhenever an elimination dirties a neighbor's derivative bounds. - Optional guarded degree-3 star–triangle (
:star_triangle): disabled by default (enable_star_triangle=false); when enabled and cheap passes are quiescent, applies at most one zero-field degree-3 elimination before returning to:dominanceand:elimination. - Bounded pair relations (
:relations): when earlier passes are quiescent, examines active relation candidates underrelation_work_budgetandmax_fill/max_total_fill, applying at most one signed contraction before returning to:dominanceand:elimination.
ScheduleReport records per-pass summaries (passes::Vector{SchedulePassSummary}), per-family deduction counts (dominance_deductions, elimination_deductions, star_triangle_deductions, relation_deductions), introduced fill_edges, initial/residual variable and edge counts, optional_passes_disabled, and exact stop reasons (:quiescent, :work_limit, :verification_limit, :deduction_limit, :deadline, :unsupported_arithmetic, :fill_limit, :optional_pass_disabled).
audit_pipeline!(model_or_ws; ...) measures and reports PipelineAccounting with PhaseAccounting across all seven lifecycle boundaries (conversion_import, discovery, arithmetic_fallback, verification, export_phase, reconstruction, rollback_replay). Run examples/scheduler.jl for the resumable mixed schedule and scripts/scheduler_pilot.jl for the 6-mode paired ablation study (off, dominance, elimination, relations, mixed_cheap, mixed_star), retained in docs/evidence/scheduler-pilot.md and docs/evidence/scheduler-pilot.tsv.
Optional certified probing with reversible branch bounds and feasible witnesses
When cheap unary dominance is quiescent on a frustrated instance, optional trial-branch probing (prove_probing, apply_probing!, probe_variables!) can certify additional strong constant fixings using the existing reversible checkpoint/rollback trail and a verified parent-scope feasible witness:
- Witness validation (
witness_upper = U): validates a complete parent-scope assignment (original-orderAbstractVector, labelAbstractDict, orReconstruction) for domain membership and compatibility with all active caller assumptions and committed workspace reductions, then evaluates its exact direction-normalized objective $U = d \cdot E(w)$. - Reversible trial conditioning and bounded cascade (
branch_steps): takes a constant-size checkpoint, temporarily conditions on the opposite branch $x_i = \bar{w}_i$, and propagates up tomax_rounds(andmax_trial_fixes) of certified strict unary dominance steps on the trial branch. - Conservative canonical branch lower bound (
branch_lower = L): evaluates the canonical spin and positive/negative-gauge Boolean coefficient lower bounds (:intervaloutward-roundedFloat64first, falling back to:exactRational{BigInt}undermax_exact_work) on the propagated trial residual. Because the bound is defined on the canonical spin representation $(c_{\text{spin}}, h_{\text{spin}}, J_{\text{spin}})$, it is invariant under QUBO↔Ising domain conversion andDomainGaugeMaptransformations. - Strict exclusion contract (
L > U) and two-branch probing (:double_probe,:probing_pair): only when $L > U$ is the opposite branch refuted and $x_i = w_i$ certified with:strongpersistency in aProbingStep(after rolling back all trial mutations to the exact pre-probe checkpoint). Whendouble_probe=true(prove_probing,apply_probing!,probe_variables!) orcontract_relations=true(probe_variables!) /enable_probing=true(prove_relation,contract_relation!,contract_relations!), both trial branches $x_p = \text{low}$ and $x_p = 1$ of an active variable are also compared: if both branches deduce the same strong assignment $x_u = v$ viaDominanceStepchains,u => vis certified witness-free with method:double_probe; if both violating states $(s_u = -1, s_v = +\sigma)$ and $(s_u = +1, s_v = -\sigma)$ are refuted by strong trialDominanceStepchains, the 2-SAT pair equivalence $s_u = \sigma s_v$ is certified with method:probing_pair. Equal bounds ($L = U$), inconclusive bounds ($L < U$), poor witnesses, or budget/deadline interruptions (max_candidates,max_work,max_exact_work,deadline_ns) abstain and restore the workspace to its pre-probe checkpoint while charging executed work inProbingAttemptorProbingReport.
Probing is disabled in default preprocess and schedule_reductions! passes so callers who do not invoke probe_variables! or apply_probing! pay zero overhead. Because each candidate probe visits the active graph to evaluate $L$, probing only pays off when a strong primal witness is already available and cheap dominance is blocked by local frustration on a small candidate set (candidates, max_candidates, max_rounds=1).
Optional certified roof-duality pass with strong persistency
When attractive (submodular or gauge-submodular) couplings lock a cluster of variables together without any single variable having a strictly dominant worst-case unary bound $|\tilde{h}_u| > \sum_v |\tilde{J}_{uv}|$, the optional exact rational roof-duality pass (prove_roof_duality, apply_roof_duality!) can compute the Boros–Hammer–Tavares (2006) posiform / implication-network lower bound and extract strongly persistent assignments without introducing any external C++/Python dependency or floating-point capacity clipping:
- Canonical symmetric implication network ($G_{\text{imp}}$): on the direction-normalized active spin polynomial $\tilde{E}(s) = \tilde{c}_{\text{spin}} + \sum_{u \in F} \tilde{h}_u s_u + \sum_{u<v \in F} \tilde{J}_{uv} s_u s_v$, each original variable $u \in \{1,\dots,n\}$ is represented by literal vertices $x_u = 2u - 1$ ($s_u = +1$) and $\bar{x}_u = 2u$ ($s_u = -1$), plus source $S = 2n + 1$ and sink $T = 2n + 2$. Starting from the base constant $C_{\text{base}} = \tilde{c}_{\text{spin}} - \sum_{u \in F} |\tilde{h}_u| - \sum_{u<v \in F} |\tilde{J}_{uv}|$:
- for $\tilde{h}_u > 0$, directed arcs $S \to \bar{x}_u$ and $x_u \to T$ receive exact rational capacity $|\tilde{h}_u|$; for $\tilde{h}_u < 0$, directed arcs $S \to x_u$ and $\bar{x}_u \to T$ receive capacity $|\tilde{h}_u|$;
- for $\tilde{J}_{uv} < 0$ (attractive), symmetric pairs $x_u \leftrightarrow x_v$ and $\bar{x}_u \leftrightarrow \bar{x}_v$ receive capacity $|\tilde{J}_{uv}|$;
- for $\tilde{J}_{uv} > 0$ (repulsive), symmetric pairs $x_u \leftrightarrow \bar{x}_v$ and $\bar{x}_u \leftrightarrow x_v$ receive capacity $|\tilde{J}_{uv}|$.
DomainGaugeMaptransformations. - Exact flow witness, strong-persistency extraction, and residual-SCC 2-SAT pair equivalences (
contract_scc=true,:roof_scc_pair): Dinic's maximum-flow algorithm runs in exactRational{BigInt}arithmetic undermax_work,max_exact_work, anddeadline_ns. From the residual network $G_f$, forward reachability from $S$ yields the mandatory source-cut set $\mathcal{R}_S$ and backward reachability to $T$ yields the mandatory sink-cut set $\mathcal{R}_T$. By Boros–Hammer–Tavares (2006) Theorem 7, variables with $x_u \in \mathcal{R}_S \land \bar{x}_u \in \mathcal{R}_T$ take $s_u = +1$ in every scoped optimum, and variables with $\bar{x}_u \in \mathcal{R}_S \land x_u \in \mathcal{R}_T$ take $s_u = -1$ in every scoped optimum. Multiple-optimum ties (where literals lie outside $\mathcal{R}_S \cup \mathcal{R}_T$) remain unfixed in strong mode. Whencontract_scc=true(prove_roof_duality,apply_roof_duality!) orenable_roof_scc=true(prove_relation,contract_relation!,contract_relations!), Tarjan's strongly connected components are also computed on the half-integral literal subgraph $V_{1/2} = \{a \in \{1,\dots,2n\} : a \notin \mathcal{R}_S \cup \mathcal{R}_T \land \bar{a} \notin \mathcal{R}_S \cup \mathcal{R}_T\}$ using symmetrized residual capacities $R(a \to b) = r_f(a \to b) + r_f(\bar{b} \to \bar{a})$: any closed positive-residual SCC $K \subseteq V_{1/2}$ (no positive residual arcs leaving $K$ into $V_{1/2} \setminus K$ and $K \cap \bar{K} = \emptyset$) or witness-bounded bottleneck SCC with cycle bottleneck $B_{\text{cycle}}(a_u, b_v) > U_{\text{witness}} - L_{\text{roof}}$ certifies strong 2-SAT pair equivalences $s_u = \sigma s_v$ (:roof_scc_pairRelationStep). - Independent primal–dual verification (
RoofDualityStep): each recordedRoofDualityStepstoresroof_lower,max_flow, the positive flow arcsflow_edges, andbatch_fixings.verify_certificateindependently reconstructs $G_{\text{imp}}$ from raw source storage, verifies capacity bounds $0 < f_{ab} \le C_{ab}$ and flow conservation $\nabla \cdot f = 0$ at all internal vertices, recomputes $\mathcal{R}_S$ and $\mathcal{R}_T$, verifies zero residual $S$–$T$ reachability and exact primal–dual cut equality $\operatorname{val}(f) = \operatorname{Cap}(\mathcal{R}_S, V \setminus \mathcal{R}_S) = \operatorname{Cap}(V \setminus \mathcal{R}_T, \mathcal{R}_T)$, and checks literal membership in $(\mathcal{R}_S, \mathcal{R}_T)$ for every fixed variable. - Operating envelope and adopt/defer guidance:
RoofDualityAttemptandRoofDualityReportreport phase-separatedgraph_work,flow_work,verification_work, andmaterialization_workcounters. Roof duality is kept off by default inWorkspace,propagate!, andschedule_reductions!because constructing $G_{\text{imp}}$ and solving exact rational max-flow is heavier than $O(\text{touched})$ local dominance and yields zero fixings on balanced zero-field frustrated instances (:no_persistency). Callapply_roof_duality!explicitly once after cheap propagation quiesces when attractive couplings block unary dominance.
Optional certified gauge-submodular component recognition and cut pass
When a connected residual component $C \subseteq F$ has no free external neighbors and admits a bipartite spin gauge $\sigma_u \in \{-1, +1\}$ making every active quadratic coupling in $C$ attractive ($\tilde{J}'_{uv} = \sigma_u \sigma_v \tilde{J}_{uv} \le 0$), the component is gauge-submodular and can be solved directly on a compact $(|C| + 2)$-vertex $s$-$t$ network (recognize_submodular_component, recognize_submodular_components, prove_submodular_cut, apply_submodular_cut!) without constructing the doubled $(2n + 2)$-vertex implication network:
- Structural recognition (
recognize_submodular_component,recognize_submodular_components): verifies in $O(|V_C| + |E_C|)$ work that $C$ is a closed active residual component (rejecting any subset with nonzero couplings to free external neighbors as:boundary_coupled) and runs a bipartite edge-parity BFS on $\operatorname{sign}(\tilde{J}_{uv})$ to discover $\sigma_u \in \{-1, +1\}$ (rejecting odd frustrated cycles as:frustrated_cycle) before allocating any flow network. - Direct $(|C| + 2)$-vertex cut network ($G_{\text{cut}}(C, \sigma)$): in gauged spin variables $s'_a = \sigma_a s_u \in \{-1, +1\}$, assigning $a \in S_C$ corresponds to $s'_a = +1$ ($s_u = \sigma_a$) and $a \in T_C$ corresponds to $s'_a = -1$ ($s_u = -\sigma_a$). Starting from $C_{\text{comp}} = -\sum_{a=1}^{|C|} |\tilde{h}'_a| - \sum_{1 \le a < b \le |C|} |\tilde{J}'_{ab}|$, directed arcs $a \to T$ (for $\tilde{h}'_a > 0$) or $S \to a$ (for $\tilde{h}'_a < 0$) receive capacity $2|\tilde{h}'_a|$, and internal edges $a \leftrightarrow b$ receive symmetric capacity $2|\tilde{J}'_{ab}|$. Every $S$-$T$ cut $(S_C, T_C)$ is in exact bijection with a spin assignment on $C$, and $C_{\text{comp}} + \operatorname{Cap}(S_C, T_C)$ equals the exact normalized spin energy of $C$.
- Strong vs. weak persistency (
allow_weak,tie_break): from the residual network $G_f$ of the exact rational maximum flow, vertices in $C \cap (\mathcal{R}_S \cup \mathcal{R}_T)$ take the same value in every minimum cut of $C$ and are certified with:strongpersistency (the defaultallow_weak=falsemode). Whenallow_weak=true, a complete jointly optimal minimum cut of $C$ is selected deterministically viatie_break(:low,:high,:source, or:sink), tagging tied vertices $a \notin \mathcal{R}_S \cup \mathcal{R}_T$ with:weakpersistency. - Independent verification (
SubmodularCutStep):verify_certificateindependently checks that $C$ is closed in the evolving polynomial state, verifies $\sigma_u \sigma_v \tilde{J}_{uv} \le 0$ on all active edges of $C$, reconstructs $G_{\text{cut}}(C, \sigma)$, verifies flow conservation, capacity bounds, residual $S$-$T$ disconnection, and primal-dual cut equality, and verifies both:strongreachability membership and joint minimum-cut capacity equality for any:weakbatch.
Optional certified weighted Max-Cut edge and triangle preprocessing
Any active Ising / QUBO residual $\tilde{F}(t) = \tilde{c}_{\text{spin}} + \sum_{u \in F} \tilde{h}_u t_u + \sum_{u < v \in F} \tilde{J}_{uv} t_u t_v$ can be represented as a signed weighted Max-Cut instance on $G_{\text{MC}} = (\{0\} \cup F, E_{\text{cut}}, w)$ (maxcut_graph, maxcut_cut_weight, maxcut_energy, maxcut_to_spin, spin_to_maxcut) with an explicit reference vertex 0 (z_0 \in \{-1, +1\}), variable cut spins $z_u \in \{-1, +1\}$ (t_u = z_0 z_u, s_u = g_u z_0 z_u), reference weights $w_{0, u} = 2\tilde{h}_u$, internal edge weights $w_{uv} = 2\tilde{J}_{uv}$, and exact energy identity $\tilde{F}(t) = C_{\text{cut}} - \operatorname{CutWeight}(z)$:
| Rule / Literature Family | Weight & Sign Regime | Fields / Reference Vertex 0 | Proof & Reconstruction Requirement | Status in QUBOPreprocessing.jl |
|---|---|---|---|---|
Direct edge dominance (:maxcut_edge, Lange et al. 2019 / Rehfeldt et al. 2023) | Signed arbitrary Rational{BigInt} weights | Reference edges (0, u) act as unary fixings; internal edges (u, v) act as signed pair contractions | Single-vertex cut flip U = {a} with `M{ab}(\sigma) = -\sigma J{ab} - \sum_{d \notin {a, b}} | J_{ad} |
External-degree-aware triangle rule (:maxcut_triangle, subset flip U = {a} \cup S_{\text{flip}}) | Signed arbitrary weights; handles both supportive and frustrated triangles | Reference vertex 0 participates as both endpoint b = 0 (unary fixing via {u, 0, c}) and triangle neighbor c = 0 ({u, v, 0}) | Each triangle {a, b, c} contributes `\gamma_{abc}(\sigma) = \max(- | J_{ac} |
Multicut / correlation-clustering triangle rule without external vertex slack R_c^{(ab)} (Lange et al. 2019 Multicut Theorem 1) | Valid for unconstrained edge-indicator multicut, unsound on signed vertex-constrained Max-Cut when R_c^{(ab)} > 0 | Ignores pinning of c by reference edge (0, c) or external couplings (c, d) | Counterexample in test/maxcut.jl shows `-J_{12} + \min( | J_{13} |
| Unweighted / nonnegative graph-bipartition degree parity & clique rules (Ferizovic et al. 2020) | Requires unit or nonnegative weights (w_{uv} \ge 0) and zero reference star (w_{0, u} = 0) | Breaks when nonzero fields create a dense signed star at vertex 0 | Requires special-case unweighted verification | Deferred (general Ising residuals have signed weights and nonzero reference star) |
Operating envelope and reference-node degree growth
- Reference-node degree (
initial_reference_degree,residual_reference_degree): every nonzero linear field $\tilde{h}_u \ne 0$ creates an edge $(0, u)$ incident to the reference vertex0. Contracting a zero-field variable into a nonzero-field representative leavesreference_degreeunchanged, whereas contracting two nonzero-field variables decreasesreference_degreeby1(or2on exact cancellation).MaxCutReportrecords bothinitial_reference_degreeandresidual_reference_degreealongsidefill_edges,triangles_used,graph_work,triangle_work, andmaterialization_work. - Default policy (opt-in optional pass): because triangle scanning inspects common-neighbor incidences (
bounded by max_trianglesandmax_fill),apply_maxcut!is kept off by default inWorkspace,propagate!, andschedule_reductions!. Callprove_maxcutorapply_maxcut!explicitly when dense triangles block single-endpoint dominance and pair relations.
Exact coefficient compression and sparsification audit (#21)
Issue #21 audits published dynamic-range compression and sparsification rules (specifically Mücke, Gerlach & Piatkowski 2023, Optimum-Preserving QUBO Parameter Compression, Definition 3 and Theorem 2, arXiv:2307.02195, and the MIT-licensed reference implementation in qubolite/preprocessing.py at commit cbe57e0bea68e9f751f8591e3ba0254030ac5965) against QUBOPreprocessing.jl's residual-to-original reconstruction contract $\operatorname{lift}(\operatorname{opt}(F')) \subseteq \operatorname{opt}(F)$ (qubolite_compression_candidates, compression_metrics, audit_compression, compression_counterexamples, CompressionCandidate, CompressionMetrics, CompressionAuditReport):
- Published update rule restated: for a normalized Boolean minimization QUBO $F(x) = C + \sum_i L_i x_i + \sum_{i < j} Q_{ij} x_i x_j$ with 1-hop partial-derivative bounds $c_i^- = \sum_{j \ne i} \min(0, Q_{ij})$, $c_i^+ = \sum_{j \ne i} \max(0, Q_{ij})$, and pair-excluded bounds $c_{i,-j}^- = c_i^- - \min(0, Q_{ij})$, $c_{i,-j}^+ = c_i^+ - \max(0, Q_{ij})$, Theorem 2 of Mücke et al. (2023) compresses:
- Diagonal entries $L_i \mapsto L_i' = -c_i^- + \tau$ when $L_i + c_i^- \ge \tau$ (or $L_i' = -c_i^+ - \tau$ when $L_i + c_i^+ \le -\tau$), and
- Off-diagonal entries $Q_{ij} > 0 \mapsto Q_{ij}' = \min_{a \in \{i,j\}} \max(0, -L_a - c_{a,-b}^- + \tau)$ when $L_a + c_{a,-b}^- + Q_{ij} \ge \tau$ (and analogously for $Q_{ij} < 0$), where $\tau = 0$ at the
:closedendpoint and $\tau = \epsilon > 0$ at the:openinterior.
- Exact optimum-set relations and counterexamples (
compression_counterexamples()):- Closed endpoints (
\tau = 0) introduce suboptimal ties (:introduced_suboptimal_tie): setting $L_i' = -c_i^-$ or $Q_{ij}' = -L_a - c_{a,-b}^-$ proves only $\operatorname{opt}(F) \subseteq \operatorname{opt}(F')$ (weak intersection), not $\operatorname{opt}(F') \subseteq \operatorname{opt}(F)$. On $F(x_1) = x_1 \to F'(x_1) = 0$ (endpoint_tie) and $F(x_1, x_2) = -x_1 - x_2 + 3 x_1 x_2 \to Q_{12}' = 1$ (quadratic_endpoint_tie), suboptimal states become globally optimal in $F'$; re-evaluating their original energy does not turn them into optimal solutions. - Negative coupling compression can lose all original optima (
:disjoint_optimum_sets): on $F(x_1, x_2) = 2 x_1 + 2 x_2 - 5 x_1 x_2$ (negative_quadratic_lost_optimum), even with open interior $\tau = 1/10 > 0$, increasing $Q_{12} = -5 \mapsto -21/10$ preserves 1-bit flip optimality at $(1, 1)$ relative to $(0, 1)$ and $(1, 0)$, but raises $F'(1, 1) = +19/10$ above the 2-bit flip $F'(0, 0) = 0$, yielding $\operatorname{opt}(F) = \{[1, 1]\}$ and $\operatorname{opt}(F') = \{[0, 0]\}$ (shared_optima_count == 0). - Strict interior compression is subsumed by exact
#14/#15elimination (strict_interior_subsumed): a diagonal update preserves $\operatorname{opt}(F') = \operatorname{opt}(F)$ via 1-hop bounds if and only if $L_i + c_i^- > 0$ or $L_i + c_i^+ < 0$—in which caseprove_dominance/apply_dominance!(#14) already fixes $x_i$ with:strongpersistency and eliminates $x_i$ and all incident couplings $Q_{ij}$ with an exact constant-shift certificate. Similarly, for $Q_{ij} > 0$, $c_{a,-b}^- = c_a^-$, so open-interval positive coupling compression can reach $Q_{ij}' = 0$ (sparsification) if and only if $L_a + c_a^- \ge \epsilon > 0$ (i.e., $x_a = 0$ is already unary-fixable by#14). - Non-constant energy transport: any nonzero in-place coefficient shift $\delta_i x_i + \delta_{ij} x_i x_j$ produces a state-dependent energy change (
constant_energy_shift == false) and weakens global lower bounds by $\min_x (F(x) - F'(x)) = -\sum_i \max(0, \delta_i) - \sum_{i<j} \max(0, \delta_{ij})$.
- Closed endpoints (
- Adopt / revise / defer decision:
- Adopted via exact elimination (
decision === :adopt_via_exact_elimination): whenever strict 1-hop bounds hold (subsumed_by_dominance == true), use the existing certified#14unary dominance or#15pair contraction passes rather than in-place coefficient clipping. - Deferred for general in-place coefficient compression (
decision === :defer): general in-place coefficient clipping/compression without variable or pair elimination is not added toWorkspace,propagate!,preprocess, orReductionCertificatebecause closed endpoints violate $\operatorname{lift}(\operatorname{opt}(F')) \subseteq \operatorname{opt}(F)$, negative coupling compression can lose all original optima, non-unary-dominated positive couplings cannot be sparsified by 1-hop bounds, and energy transport is state-dependent.
- Adopted via exact elimination (
Kernel-checked Lean 4 formalization (#54, #68, #72, #74, #76)
The directory lean/ provides a standalone Lean v4.33.1 / Mathlib v4.33.1 formalization (lean/verify.sh, lean/verification/result.json) of all eight core theoretical results on this page across nine modules (180 public source theorems, 360 total compiled constants, with zero compiler warnings and using only Lean's standard foundational axioms propext, Classical.choice, and Quot.sound):
QUBOPreprocessing.GaugeCoercive(Proposition 1,#54): QUBO↔Ising affine bijection, exact $n$-variable energy equivalence, spin-flip gauge invariance of $|h_i|$, $|J_{ij}|$, $\sum_{j \ne i} |J_{ij}|$, and coercive-field ratios $\rho_i$, equivalence of Hammer–Hansen–Simeone binary derivative bounds and Ising coercive-field criteria, and soundness of coercive-field fixing.QUBOPreprocessing.CompositionRepair(Theorem 2 & Corollary 2.1,#54): Compositional closure of weak and strong preprocessing reduction steps (ReductionStep.comp,StrongReductionStep.comp), monotonic and strictly improving post-processing repair (repair_monotone,repair_strict_improvement), and exact 8-state zero-field degree-3 Ising star–triangle elimination (starMin_cubic_walsh_zero,starTriPoly_eq_starMin).QUBOPreprocessing.MaxCutTriangle(Proposition 3,#54): External-degree-aware Max-Cut triangle slack $\gamma_{abc}(\sigma)$ (gammaTriangle), supportive and frustrated closed forms, soundness of single-spin vs. joint triangle co-flip dominance (maxcut_triangle_dominance_sound,maxcut_triangle_strict_improvement), and the formal counterexample refuting the uncorrected multicut triangle rule when $R_c > 0$ (uncorrected_multicut_triangle_counterexample).QUBOPreprocessing.CompressionAudit(Theorem 4,#54): Formal refutations of closed-endpoint and open-interior negative-coupling parameter compression (endpoint_tie_counterexample,quadratic_endpoint_tie_counterexample,negative_quadratic_lost_optimum_counterexample), subsumption of valid open-interior diagonal compression and positive-coupling sparsification by strict unary dominance (diagonal_compression_subsumed_by_dominance,positive_quadratic_sparsification_subsumed_by_dominance), and non-constant energy transport of in-place coefficient perturbations (in_place_compression_nonconstant_shift).QUBOPreprocessing.WalshDegree3(Theorem 5,#68): General 8-point Walsh–Hadamard decomposition on $\{-1, +1\}^3$ (walshQuadPoly_add_cubic_eq,walshQuadPoly_eq_iff_cubic_zero), general non-zero-field degree-3 spin marginalization (deg3StarMin_eq_walshQuadPoly_iff_cubic_zero,deg3Star_elimination_is_reduction), the full-dimensional $\alpha_{123} = 0$ trichotomy cones (deg3StarMin_cubic_zero_of_h0_zero,deg3StarMin_cubic_zero_of_field_dominant,deg3StarMin_cubic_zero_of_heavy_edge1–3), and cubic obstructions certifying:nonquadratic_elimination.QUBOPreprocessing.CoflipCancellation(Theorem 6,#72): Exact two-spin co-flip average identity (coflip_average_eq), shared-neighborhood cancellation radius and strong/weak:coflip_pairpersistency (coflip_pair_strong_persistency,coflip_pair_weak_persistency), coupled and non-adjacent twin contraction (coupled_twin_strong_contraction,nonadjacent_twin_weak_contraction), monotone one-sided $L_1$ pruning increments (one_sided_diff_sum_eq,coflipDelta_nonneg), andReductionStep/StrongReductionStepbridges (coflip_reductionStep,coflip_strongReductionStep).QUBOPreprocessing.ProbingMargin(Theorem 7,#74): Single-step spin margin and Boolean-to-spin normalization (boolToSpinMargin_eq,single_step_spin_margin_sound), first-divergence and full-cascade telescoping trial-dominance repair (cascade_first_divergence_repair,cascadeFullRepair_satisfies_and_telescopes,cascadeFullRepair_drop_ge_branchSpinMargin), witness-free:double_probe(double_probe_sound,double_probe_reductionStep,double_probe_strongReductionStep), and 4-pattern 2-SAT:probing_pairequivalence (probing_pair_sound,probing_pair_reductionStep,probing_pair_strongReductionStep).QUBOPreprocessing.BlockElimination(Theorem 8,#76): Separator-conditioned connected block marginalization (block_elimination_reductionStep,block_elimination_unique_argmin_iff,block_elimination_strongReductionStep), universal exactness of 0-, 1-, and 2-separator Boolean and Spin quadratic interpolation (interp0Poly_eq,bool1Poly_eq,spin1Poly_eq,bool2QuadPoly_eq,spin2QuadPoly_eq), batch $k$-step zero-delta materialization and coordinate-wise table reconstruction (sum_batchStepDelta_eq,reconstruct_coordBlockTable_eq), and concrete 0-, 1-, 2-, and ($\alpha_{123} = 0$) 3-separatorReductionStep/StrongReductionSteptheorems.