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}|$.

  1. 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$ (:weak with allow_weak=true).
  2. 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.
    Taking the branch with the larger lower bound $\text{lo}_{\text{glk}}$, $\text{lo}_{\text{glk}} > 0$ certifies :strong persistency and $\text{lo}_{\text{glk}} == 0$ (when allow_weak=true and $\text{center} > 0$) certifies :weak persistency.
  3. 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 :strong persistency (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$ with allow_weak=true certifies :weak persistency (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).
  4. 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:

  1. $h_u = 0$ (zero-field star–triangle reduction, Eq. 4);
  2. $|h_u| \ge |J_1| + |J_2| + |J_3|$ (unary coercive-field dominance, introducing 0 fill edges); or
  3. $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 to max_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:

LimitCharged work
max_workcandidate checks plus deduction-update adjacency visits
max_deductionscommitted deductions
max_exact_workcached sign checks and conservative reservations of one constant plus three exact values per incident edge for an attempted update
deadline_nsabsolute 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-vertex K_5): elim_queues are initially empty (0 candidates examined, 0 edge visits, 32 -> 32 states). End-to-end on (including workspace construction and residual export) takes 1100.78 µs (401.4 KiB) vs 650.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-<= 2 vertex halves the exhaustive child search (32 -> 16 states), but workspace construction, exact Rational{BigInt} table certification, proof verification and residual materialization take 481.00 µs (255.2 KiB) vs 287.09 µs (257.4 KiB) off (median paired +199.98 µs).
  • Break-even and sparse payoff (whisker_7, whisker_10, and cycle_8): each eliminated degree-<= 2 vertex halves the downstream exponential search space at O(touched) local cost (<= 4 boundary evaluations per vertex), crossing end-to-end break-even against the exact-enumeration child at 3 eliminated variables (whisker_7, 128 -> 16 states, 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 -> 16 states, 29738.92 -> 2094.45 µs, median paired −18940.16 µs, 13622.6 -> 502.2 KiB), and solving cycle_8 completely where strict dominance removes 0 variables (256 -> 1 state, 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): on zero_field_k4 (n = 4), deg3 solves the graph completely (16 -> 1 state, 10/20/37 candidate/edge/exact work), but on 16 states the 8-state Rational{BigInt} table certification costs more than direct enumeration (+1707.74 µs vs off, +667.38 µs vs deg2). On zero_field_wheel_w6 (n = 6, 64 -> 16 states, −552.97 µs vs deg2) and zero_field_subdivided_10 (n = 10, 1024 -> 256 states under deg2 vs 1024 -> 32 states under deg3, 10192.32 -> 2173.07 µs, median paired −7903.97 µs vs deg2 and −133860.71 µs vs off), 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), deg3 rejects the hub in O(1) with 0 additional edge visits and 0 additional exact table work (12/1/13 vs 10/1/13); when the induced shift cancels the center field to 0 (conditioned_unlocked_8), deg3 unlocks star–triangle reduction and cascades (128 -> 16 states, 4635.77 -> 1958.97 µs, median paired −2799.52 µs vs deg2).
  • No-benefit nonzero-field control (no_benefit_cubic_8): on a 3-regular cube where all 8 degree-3 vertices have nonzero fields, deg3 rejects all 8 candidates in O(1) with 0 edge visits and 0 exact table work (8/0/0 work vs 0/0/0 under deg2, +926.23 µs vs deg2).

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:

  1. Cheap dirty-neighborhood propagation (:dominance): drains all dirty unary dominance candidates (st.queue).
  2. Degree-<= 2 local elimination (:elimination): drains buckets 1..3 (degrees 0, 1, 2) under max_fill / max_total_fill, immediately cascading back to :dominance whenever an elimination dirties a neighbor's derivative bounds.
  3. 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 :dominance and :elimination.
  4. Bounded pair relations (:relations): when earlier passes are quiescent, examines active relation candidates under relation_work_budget and max_fill / max_total_fill, applying at most one signed contraction before returning to :dominance and :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:

  1. Witness validation (witness_upper = U): validates a complete parent-scope assignment (original-order AbstractVector, label AbstractDict, or Reconstruction) 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)$.
  2. 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 to max_rounds (and max_trial_fixes) of certified strict unary dominance steps on the trial branch.
  3. Conservative canonical branch lower bound (branch_lower = L): evaluates the canonical spin and positive/negative-gauge Boolean coefficient lower bounds (:interval outward-rounded Float64 first, falling back to :exact Rational{BigInt} under max_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 and DomainGaugeMap transformations.
  4. 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 :strong persistency in a ProbingStep (after rolling back all trial mutations to the exact pre-probe checkpoint). When double_probe=true (prove_probing, apply_probing!, probe_variables!) or contract_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$ via DominanceStep chains, u => v is 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 trial DominanceStep chains, 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 in ProbingAttempt or ProbingReport.

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:

  1. 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}|$.
    Because $(\tilde{c}_{\text{spin}}, \tilde{h}_u, \tilde{J}_{uv})$ is the unique symmetric normal form of the quadratic pseudo-Boolean function, $G_{\text{imp}}$ and $L_{\text{roof}} = C_{\text{base}} + \operatorname{MaxFlow}(G_{\text{imp}})$ are strictly invariant under binary↔spin domain conversion and DomainGaugeMap transformations.
  2. 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 exact Rational{BigInt} arithmetic under max_work, max_exact_work, and deadline_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. When contract_scc=true (prove_roof_duality, apply_roof_duality!) or enable_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_pair RelationStep).
  3. Independent primal–dual verification (RoofDualityStep): each recorded RoofDualityStep stores roof_lower, max_flow, the positive flow arcs flow_edges, and batch_fixings. verify_certificate independently 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.
  4. Operating envelope and adopt/defer guidance: RoofDualityAttempt and RoofDualityReport report phase-separated graph_work, flow_work, verification_work, and materialization_work counters. Roof duality is kept off by default in Workspace, propagate!, and schedule_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). Call apply_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:

  1. 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.
  2. 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$.
  3. 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 :strong persistency (the default allow_weak=false mode). When allow_weak=true, a complete jointly optimal minimum cut of $C$ is selected deterministically via tie_break (:low, :high, :source, or :sink), tagging tied vertices $a \notin \mathcal{R}_S \cup \mathcal{R}_T$ with :weak persistency.
  4. Independent verification (SubmodularCutStep): verify_certificate independently 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 :strong reachability membership and joint minimum-cut capacity equality for any :weak batch.

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 FamilyWeight & Sign RegimeFields / Reference Vertex 0Proof & Reconstruction RequirementStatus in QUBOPreprocessing.jl
Direct edge dominance (:maxcut_edge, Lange et al. 2019 / Rehfeldt et al. 2023)Signed arbitrary Rational{BigInt} weightsReference edges (0, u) act as unary fixings; internal edges (u, v) act as signed pair contractionsSingle-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 trianglesReference 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)} > 0Ignores 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 0Requires special-case unweighted verificationDeferred (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 vertex 0. Contracting a zero-field variable into a nonzero-field representative leaves reference_degree unchanged, whereas contracting two nonzero-field variables decreases reference_degree by 1 (or 2 on exact cancellation). MaxCutReport records both initial_reference_degree and residual_reference_degree alongside fill_edges, triangles_used, graph_work, triangle_work, and materialization_work.
  • Default policy (opt-in optional pass): because triangle scanning inspects common-neighbor incidences (bounded by max_triangles and max_fill), apply_maxcut! is kept off by default in Workspace, propagate!, and schedule_reductions!. Call prove_maxcut or apply_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):

  1. 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 :closed endpoint and $\tau = \epsilon > 0$ at the :open interior.
  2. 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/#15 elimination (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 case prove_dominance / apply_dominance! (#14) already fixes $x_i$ with :strong persistency 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})$.
  3. 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 #14 unary dominance or #15 pair 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 to Workspace, propagate!, preprocess, or ReductionCertificate because 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.

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_pair persistency (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), and ReductionStep / StrongReductionStep bridges (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_pair equivalence (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-separator ReductionStep / StrongReductionStep theorems.