API
For a complete sequence of calls, start with the user guide. This page lists individual interfaces for looking up arguments and return contracts.
Qualified optimizer factory
The optional solver factory is used as QUBOPreprocessing.Optimizer so that it can share a session with other solver packages. It becomes available after loading QUBODrivers.
QUBOPreprocessing.Optimizer — Function
QUBOPreprocessing.Optimizer(fresh_child_factory; kwargs...)Optional QUBODrivers/MOI optimizer factory, available after loading QUBODrivers. Use () -> QUBOPreprocessing.Optimizer(child_factory; ...) with MOI/JuMP/ToQUBO. The factory is accessed by its qualified name to avoid solver namespace collisions. It shares the sample_preprocessed implementation, snapshots the accepted compiled QUBO on each solve, restores every logical QUBO variable before source decoding, and reports the public child's proof status conservatively. A compiled optimum does not establish source-model feasibility. Core workspace use has no mandatory QUBODrivers, JuMP, ToQUBO or concrete solver dependency.
Exported API
QUBOPreprocessing.BudgetedFamilyRun — Type
BudgetedFamilyRunOne reduction family's share of a schedule_budgeted! run: family (:cheap, :roof_duality, :submodular_cut, :maxcut, :blocks, :roof_scc or :probing), number of calls, wall-clock time_s, variables it removed (freed) and the stop_reason of its last call.
QUBOPreprocessing.BudgetedScheduleReport — Type
BudgetedScheduleReportReturned by schedule_budgeted!: stop_reason (:fixpoint when every family finished on the final workspace without removing a variable, :solved when no free variable remains, or :deadline when time_limit expired first), number of passes, wall-clock elapsed_s, initial_variables, residual_variables and the per-family families in schedule order.
QUBOPreprocessing.Checkpoint — Type
CheckpointOpaque workspace/source/branch-specific position in the conditioning trail. An ancestor remains valid after rollback; discarded descendants cannot become valid again after a new branch reaches the same depth. Reset and non-LIFO unfix invalidate checkpoints. Private fields are not a construction/mutation API.
QUBOPreprocessing.CompressionAuditReport — Type
CompressionAuditReport{V}Bounded exact audit report comparing an original model $F$ against a coefficient-compressed or sparsified model $F'$ under QUBOPreprocessing.jl's residual-to-original guarantee $\operatorname{lift}(\operatorname{opt}(F')) \subseteq \operatorname{opt}(F)$.
Fields:
stop_reason::Symbol::audited,:variable_limit_exceeded, or:work_limit_exceededrelation::Symbol::exact_optimum_set($\operatorname{opt}(F') = \operatorname{opt}(F)$):optimum_preserving_subset($\emptyset \ne \operatorname{opt}(F') \subsetneq \operatorname{opt}(F)$):introduced_suboptimal_tie($\operatorname{opt}(F) \subsetneq \operatorname{opt}(F')$; violates residual-to-original reconstruction because $\operatorname{opt}(F') \setminus \operatorname{opt}(F) \ne \emptyset$):partial_overlap_with_suboptimal($\operatorname{opt}(F) \cap \operatorname{opt}(F') \ne \emptyset$, but neither set contains the other; violates residual-to-original reconstruction):disjoint_optimum_sets($\operatorname{opt}(F) \cap \operatorname{opt}(F') = \emptyset$; all original global optima are lost):unverified(audit budget or variable cap exceeded before exhaustive check)
residual_to_original_valid::Bool:trueiffstop_reason === :auditedand every optimal state of $F'$ is also globally optimal in $F$ ($\emptyset \ne \operatorname{opt}(F') \subseteq \operatorname{opt}(F)$)constant_energy_shift::Bool:trueiff $F(x) - F'(x)$ is constant across all $2^n$ feasible statesoptimal_energy_shift::Union{Nothing,Rational{BigInt}}: exact shift $F(x^*) - F'(x^*)$ when constant across $x^* \in \operatorname{opt}(F')$, elsenothingvalid_lower_bound_shift::Rational{BigInt}: exact worst-case bound shift $\min_{x} (F(x) - F'(x))$ on normalized minimization energyoriginal_optimal_value::Rational{BigInt}: exact optimal objective value of $F$ (in user sense/scale/offset)transformed_optimal_value::Rational{BigInt}: exact optimal objective value of $F'$ (in user sense/scale/offset)worst_lifted_original_value::Rational{BigInt}: worst original objective value $F(x')$ among $x' \in \operatorname{opt}(F')$original_optima_count::Int,transformed_optima_count::Int,shared_optima_count::Intintroduced_suboptimal_witness::Union{Nothing,Vector{Int}}: state $x' \in \operatorname{opt}(F') \setminus \operatorname{opt}(F)$ if anylost_optimum_witness::Union{Nothing,Vector{Int}}: state $x^* \in \operatorname{opt}(F) \setminus \operatorname{opt}(F')$ if anysubsumed_by_dominance::Bool: whether all sound candidates in this transformation are already subsumed by exact unary fixing (#14) or pair contraction (#15)subsuming_rule::Symbol::none,:zero_noop,:unary_dominance, or:pair_dominancedecision::Symbol::defer,:adopt_via_exact_elimination, or:noopmissing_proof::Symbol: explicit mathematical reason why in-place coefficient compression is deferredcandidates::Vector{CompressionCandidate{V}}metrics::CompressionMetricsstates_evaluated::Int,bound_work::Int,verification_work::Int,reconstruction_work::Int,total_work::Int
QUBOPreprocessing.CompressionCandidate — Type
CompressionCandidate{V}Bounded local coefficient-compression candidate audited under Issue #21 (Mücke, Gerlach & Piatkowski 2023, Optimum-Preserving QUBO Parameter Compression, Definition 3 and Theorem 2, arXiv:2307.02195; audited against qubolite reduce_dynamic_range at commit cbe57e0bea68e9f751f8591e3ba0254030ac5965).
Fields:
kind::Symbol::linear(diagonal $L_i \mapsto L_i'$) or:quadratic(off-diagonal $Q_{ij} \mapsto Q_{ij}'$)variables::Tuple{V,Union{Nothing,V}}:(u, nothing)for:linear,(u, v)for:quadraticindices::Tuple{Int,Int}:(i, 0)for:linear,(i, j)(i < j) for:quadraticrule::Symbol::qubolite_linear_closed,:qubolite_linear_open,:qubolite_quadratic_pos_closed,:qubolite_quadratic_pos_open,:qubolite_quadratic_neg_closed,:qubolite_quadratic_neg_open, or:customendpoint::Symbol::closed(\epsilon = 0) or:open(\epsilon > 0)original_coeff::Rational{BigInt}: exact normalized Boolean minimization coefficient before updatecompressed_coeff::Rational{BigInt}: exact normalized Boolean minimization coefficient after updatedelta::Rational{BigInt}:compressed_coeff - original_coefflower_bound::Rational{BigInt}: local 1-hop derivative lower bound (c_i^-orc_{a,-b}^-)upper_bound::Rational{BigInt}: local 1-hop derivative upper bound (c_i^+orc_{a,-b}^+)strict_local_dominance::Bool: whether strict 1-hop local dominance (L_i + c_i^- > 0,L_i + c_i^+ < 0, or pair implicationx_i x_j = 0) already holds in the original modelsubsuming_rule::Symbol::none,:unary_dominance(#14), or:pair_dominance(#15)
QUBOPreprocessing.CompressionMetrics — Type
CompressionMetricsExact sparsity and dynamic-range comparison between an original QUBO/Ising model and a coefficient-transformed model in normalized Boolean minimization form.
dynamic_range is defined as max_abs_coeff // min_abs_nonzero when at least one nonzero linear or quadratic coefficient exists, and 0 // 1 when all coefficients are zero.
QUBOPreprocessing.ConditionedExport — Type
ConditionedExportOwned historical residual under explicit caller assumptions and/or certified deductions. status=:certified certifies exact algebra/transport within that scope, not that caller assumptions retain a global optimum. The certificate contains the ordered strong-deduction proof when present; no solver proof is produced. An explicitly rounded Float64 transport has status=:rounded and records its largest effective-coefficient change in max_perturbation; the reduction proof continues to describe the exact residual, not the rounded solver model. Original labels/maps, scope and exact residual data are immutable snapshots; export_model returns a separately owned QUBOTools model.
QUBOPreprocessing.DomainGaugeMap — Type
DomainGaugeMapChecked coordinate bijection between a workspace's accepted source model and a target domain (:bool or :spin) with spin gauge $s_i = g_i t_i$ where $g_i \in \{-1, +1\}$. For binary coordinates $x_i \in \{0, 1\}$ and canonical spin coordinates $s_i = 2x_i - 1 \in \{-1, +1\}$, the unscaled polynomial satisfies $J_{ij} = b_{ij}/4$, $h_i = a_i/2 + \sum_{j \ne i} b_{ij}/4$ and $c_{\text{spin}} = c_{\text{bool}} + \frac{1}{2}\sum_i a_i + \frac{1}{4}\sum_{i<j} b_{ij}$. Under gauge $g_i$, spin fields transform as $h'_i = g_i h_i$ and couplings as $J'_{ij} = g_i g_j J_{ij}$ with unchanged spin constant. Target binary coordinates relate to gauged spins by $t_i = 2u_i - 1$.
Retains generation, source_domain, target_domain, sense, scale, offset, gauge and ordered source identity. This is a bijective coordinate map, not a variable fixing, local elimination or symmetry-breaking selection; optional gauge selection transforms fields rather than assuming zero fields.
QUBOPreprocessing.DominanceAttempt — Type
Proof attempt with optional certificate, stop_reason, numeric method, adjacency edge_visits, and explicit exact_fallbacks/exact_work counters.
QUBOPreprocessing.DominanceCertificate — Type
DominanceCertificateOwned source/generation, explicit caller scope and ordered reduction steps (DominanceStep, RelationStep, EliminationStep, ProbingStep, RoofDualityStep, SubmodularCutStep, MaxCutStep). Every step retains all scoped optima (:strong) or at least one scoped optimum of the evolving residual (:weak / non-unique argmin). max_perturbation::Rational{BigInt} records the largest absolute change in any effective objective coefficient or scaled offset (including scale and offset: $\max_v |\operatorname{Rational\{BigInt\}}(\alpha_{\text{new}}) \cdot \operatorname{Rational\{BigInt\}}(v_{\text{new}}) - \operatorname{Rational\{BigInt\}}(\alpha) \cdot \operatorname{Rational\{BigInt\}}(v)|$; 0 // 1 when the source snapshot is exact), and perturbed::Bool is true iff max_perturbation > 0 // 1. Also aliased as ReductionCertificate.
QUBOPreprocessing.DominanceStep — Type
DominanceStepCompact unary dominance/persistency witness. Bounds enclose the normalized derivative (or component-marginal difference when method === :marginal) of the unscaled objective: normalization multiplies by the sign of scale and objective sense, never by a potentially overflowing magnitude. predecessors is the number of preceding steps in the ordered certificate prefix; every preceding deduction is therefore explicit without copying the chain per step. constant binds the exact conditioned offset. persistency is :strong (all optima satisfy variable == value) or :weak (at least one optimum of the current conditioned residual satisfies variable == value). Indices refer to original variable order.
QUBOPreprocessing.EliminationAttempt — Type
Local variable elimination proof attempt with optional certificate, stop_reason, numeric method, adjacency edge_visits, and exact_work.
QUBOPreprocessing.EliminationStep — Type
EliminationStepCompact bounded-degree (0 <= length(neighbors) <= 3) exact local variable or bounded-separator (0 <= length(neighbors) <= 2) connected block elimination witness certifying $F'(y) = \operatorname{opt}_{x_u} F(y, x_u)$ (or $F'(y) = \operatorname{opt}_{x_B} F(y, x_B)$ across block_witness.block_variables) across all $2^d$ boundary assignments of neighbors (stored in ascending original-index order). table stores the reconstructing original-domain assignment for variable indexed by 1 + sum(((z_b == 1) << (b - 1)) for b in 1:d). constant_delta, linear_deltas and quadratic_deltas store the exact source-domain polynomial update induced by the elimination. unique_argmin is true when the minimizing assignment is strict for every boundary configuration z.
QUBOPreprocessing.EnergyEvaluation — Type
Ordinary Float64 energy, with finite and method; it is not an exact proof.
QUBOPreprocessing.ExportResult — Type
ExportResultOwned immutable identity export, with status == :certified, original scope and an empty reduction chain. certificate.unchanged_representation is true iff the snapshot was not perturbed (result.perturbed == false). Obtain a separately owned mutable solver model with export_model. Private fields are implementation details, not a mutation API.
QUBOPreprocessing.Generation — Type
GenerationOpaque identity for one workspace and one accepted source snapshot. Equality matches both identities; it is neither a source hash nor an optimality proof.
QUBOPreprocessing.IdentityReport — Type
No-inference report: :quiescent means identity completion, never solver optimality.
QUBOPreprocessing.MaxCutAttempt — Type
Certified weighted Max-Cut edge or triangle proof attempt with optional certificate, stop_reason, method (:maxcut_edge or :maxcut_triangle), exact normalized flip margin, triangles_used, and phase-separated work counters (graph_work, triangle_work, edge_visits, exact_work).
QUBOPreprocessing.MaxCutGraph — Type
MaxCutGraph{V}Exact signed weighted Max-Cut representation of the active direction-normalized Ising residual of a Workspace:
\[\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 = C_{\text{cut}} - \sum_{(a, b) \in E_{\text{cut}}} w_{ab} \, \delta(z_a \ne z_b),\]
where reference_vertex == 0 carries spin $z_0 \in \{-1, +1\}$, each active variable $u \in F$ carries cut spin $z_u \in \{-1, +1\}$ related to gauged spin $t_u = z_0 z_u$ (and original canonical spin $s_u = g_u z_0 z_u$), reference edges have weight $w_{0,u} = 2\tilde{h}_u$, internal edges have weight $w_{uv} = 2\tilde{J}_{uv}$, and $C_{\text{cut}} = \tilde{c}_{\text{spin}} + \sum_{u \in F} \tilde{h}_u + \sum_{u < v \in F} \tilde{J}_{uv}$.
Global cut reversal $z \mapsto -z$ preserves both $\operatorname{CutWeight}(z)$ and every physical spin $s_u = g_u z_0 z_u$.
QUBOPreprocessing.MaxCutReport — Type
MaxCutReport{V,S}Report returned by apply_maxcut!, recording generation, checkpoint, stop_reason (:applied, :quiescent, :not_strict, :no_persistency, :already_fixed, :zero_scale, :fill_limit, :deduction_limit, :work_limit, :verification_limit, :deadline, or :optional_pass_disabled), examined candidates, total committed deductions, unary_fixings, pair_contractions, edge_deductions (:maxcut_edge), triangle_deductions (:maxcut_triangle), total triangles_used, introduced fill_edges, initial_reference_degree, residual_reference_degree, committed fixings, committed contractions (eliminated, representative, sign), and phase-separated work counters (graph_work, triangle_work, materialization_work, edge_visits, exact_work).
QUBOPreprocessing.MaxCutStep — Type
MaxCutStepCompact weighted Max-Cut edge or triangle preprocessing witness on the active residual Max-Cut graph $G_{\text{MC}} = (\{0\} \cup F, E_{\text{cut}}, w)$. When representative == 0, certifies the unary variable fixing eliminated => value ($s_{\text{eliminated}} = \sigma_{\text{orig}}$ via contraction with reference vertex 0). When representative > 0, certifies the signed pair contraction $s_{\text{eliminated}} = \sigma_{\text{orig}} s_{\text{representative}}$ (and $t_{\text{eliminated}} = \sigma t_{\text{representative}}$ in the active coordinate representation). anchor (eliminated or representative) records the vertex whose subset-flip neighborhood $\{a\} \cup S_{\text{flip}}$ produces the exact normalized energy-improvement lower bound margin (direct_weight + sum(t[5] for t in triangles) - non_triangle_slack). method is :maxcut_edge when isempty(triangles) and :maxcut_triangle when at least one triangle witness (c, J_ac, J_bc, R_c, gamma_c) contributes a strictly positive net gain $\gamma_c > -|J_{ac}|$.
QUBOPreprocessing.PhaseAccounting — Type
PhaseAccountingPer-phase work, exact-arithmetic, fallback, allocation and wall-time accounting for one preprocessing lifecycle boundary (:conversion_import, :discovery, :arithmetic_fallback, :verification, :export, :reconstruction, :rollback_replay).
QUBOPreprocessing.PipelineAccounting — Type
PipelineAccountingComplete end-to-end accounting across all seven preprocessing lifecycle phases (conversion_import, discovery, arithmetic_fallback, verification, export_phase, reconstruction, rollback_replay), together with initial and residual graph dimensions (initial_variables, residual_variables, initial_edges, residual_edges), introduced fill_edges, verified certificate status, and the underlying report (ScheduleReport, PropagationReport or IdentityReport).
QUBOPreprocessing.PolicyScheduleReport — Type
PolicyScheduleReportVersioned report from schedule!. policy/policy_version identify the algorithm, settings retain its effective options and dispatch dimensions, and families aggregate calls, seconds, variables removed (freed) and last stop reasons. deductions counts removed variables. skipped_families are disabled by the selected policy, not claimed to be at a fixpoint. Timing covers scheduling only; import, materialization and independent replay are separate. For legacy policies, passes counts entered expensive-family outer rounds; the initial reductions call is present in families even when passes == 0.
QUBOPreprocessing.ProbingAttempt — Type
Certified probing proof attempt with optional certificate, stop_reason, numeric method, adjacency edge_visits, and explicit exact_fallbacks/exact_work counters.
QUBOPreprocessing.ProbingReport — Type
ProbingReportBounded-call probing result with generation, checkpoint, stop_reason, probed candidates, edge_visits, committed deductions, exact_fallbacks, exact_work, remaining pending candidate count, and cumulative workspace totals. Counters measure executed work and are not undone by model rollback.
QUBOPreprocessing.ProbingStep — Type
ProbingStepCompact trial-branch probing witness certifying variable == value. For method in (:interval, :exact), refutes the opposite assignment variable == probed_value (probed_variable == variable) against a verified parent-scope feasible witness witness_state with normalized energy witness_upper (branch_lower > witness_upper, persistency === :strong). For method === :double_probe, certifies a witness-free common unary deduction variable == value reached under both branches of probed_variable (probed_variable => low_orig in branch_steps with bottleneck spin margin branch_lower > 0, and probed_variable => 1 in alt_branch_steps with bottleneck spin margin witness_upper > 0).
QUBOPreprocessing.PropagationReport — Type
PropagationReportBounded-call result with generation/checkpoint, stop_reason, examined candidates, edge_visits, new deductions, reserved exact_work, raw pending queue entries and cumulative propagation totals. Counters measure executed/reserved work and are not undone by model rollback. Caller updates, initial construction, proof export and verification remain separate boundaries.
QUBOPreprocessing.Reconstruction — Type
Complete owned original-order state, numerical energy, and historical generation.
QUBOPreprocessing.ReductionCertificate — Type
ReductionCertificateAlias for DominanceCertificate representing an ordered certificate chain of unary dominance restrictions, signed pair relation contractions, bounded-degree exact variable eliminations, and certified probing steps.
QUBOPreprocessing.RelationAttempt — Type
Relation proof attempt with optional certificate, stop_reason, numeric method, adjacency edge_visits, and explicit exact_fallbacks/exact_work counters.
QUBOPreprocessing.RelationStep — Type
RelationStepCompact signed pair relation witness certifying the substitution $s_{\text{eliminated}} = \sigma_{\text{orig}} s_{\text{representative}}$ in original canonical spin coordinates (equivalently $x_u = x_v$ for $\sigma_{\text{orig}} = +1$ and $x_u = 1 - x_v$ for $\sigma_{\text{orig}} = -1$ in binary coordinates), and $t_{\text{eliminated}} = \sigma t_{\text{representative}}$ (sign) in the certificate's active coordinate representation. For method in (:interval, :exact), lower and upper enclose the normalized single-flip spin energy difference $-\sigma \tilde{J}_{uv} \mp (|\tilde{h}_u| + \sum_{w \ne v} |\tilde{J}_{uw}|)$. For method === :glk_pair, lower and upper record the exact Glover–Lewis–Kochenberger cross-endpoint flip margins ruling out the two violating states $(t_u, t_v) \in \{(-\sigma, +1), (+\sigma, -1)\}$. For method === :coflip_pair, lower and upper record the exact shared-neighborhood co-flip bounds $-\sigma \tilde{J}_{uv} \mp \frac{1}{2}(|\tilde{h}_u - \sigma \tilde{h}_v| + \sum_{w \notin \{u,v\}} |\tilde{J}_{uw} - \sigma \tilde{J}_{vw}|)$. For method === :probing_pair, lower and upper record the ordered bottleneck spin dominance margins of the two trial dominance cascades in witness::_ProbingPairWitness refuting the two violating assignments $(s_u, s_v) \in \{(-1, +\sigma_{\text{orig}}), (+1, -\sigma_{\text{orig}})\}$. For method === :roof_scc_pair, lower and upper record the exact residual cycle bottleneck flip margin $B_{\text{cycle}} - \Delta > 0$ certified by the roof-duality implication-network residual SCC in witness::_RoofSCCPairWitness. persistency is :strong when lower > 0 and :weak when lower == 0.
QUBOPreprocessing.RollbackReport — Type
RollbackReportOptional owned rollback result: source generation, restored checkpoint, caller_unfixed and deduction_unfixed vectors of original-index => removed-value pairs in reverse application order. These are indices, unlike the label-based assumptions/deductions queries. They describe removals, not new proof claims.
QUBOPreprocessing.RoofDualityAttempt — Type
Certified roof-duality proof attempt with optional certificate, stop_reason, method, exact normalized lower_bound, scaled objective_bound, implication-network max_flow, strongly persistent fixings, phase-separated work counters, and optional residual SCC pair contractions (contracted_count).
QUBOPreprocessing.RoofDualityReport — Type
RoofDualityReport{V,S}Summary of an optional certified apply_roof_duality! pass, recording stop_reason, exact normalized lower_bound, scaled model objective_bound, implication-network max_flow, fixed_count, committed fixings, phase-separated work counters (graph_work, flow_work, verification_work, materialization_work, edge_visits, exact_work), and optional residual-SCC 2-SAT pair contractions (contracted_count, contractions).
QUBOPreprocessing.RoofDualityStep — Type
RoofDualityStepRecorded strongly persistent variable-fixing proof step derived from the exact rational implication-network (posiform / roof-duality) relaxation on the active residual model.
QUBOPreprocessing.SchedulePassSummary — Type
SchedulePassSummaryPer-pass execution summary recorded by schedule_reductions!: pass (:dominance, :elimination, :star_triangle or :relations), stop_reason, examined candidates, edge_visits, committed deductions, reserved/executed exact_work, exact_fallbacks, and new fill_edges added during the pass.
QUBOPreprocessing.ScheduleReport — Type
ScheduleReportBounded mixed-pass scheduling report returned by schedule_reductions!. Retains generation, checkpoint, stop_reason (:quiescent, :work_limit, :verification_limit, :deduction_limit, :deadline, :unsupported_arithmetic, :fill_limit or :optional_pass_disabled), total candidates, edge_visits, deductions, exact_work, exact_fallbacks, pending, cumulative totals, per-family deduction counts (dominance_deductions, elimination_deductions, star_triangle_deductions, relation_deductions), total introduced fill_edges, initial/residual graph sizes (initial_variables, residual_variables, initial_edges, residual_edges), ordered passes::Vector{SchedulePassSummary}, and optional_passes_disabled.
QUBOPreprocessing.SolverResult — Type
SolverResultOwned direct-consumer evidence. samples contain complete original-order reconstructions and reads their multiplicities. optimal applies only to the original scope; scope_optimal can instead certify the retained caller scope. stop_reason, public child_status, generation, captured exported residual, and metadata retain work/timing/proof/capacity information. workspace is the live workspace used for the call; captured exports/samples remain historical when that workspace changes. A timeout can retain validated samples without an optimality claim. No missing free values are invented.
QUBOPreprocessing.SubmodularComponent — Type
SubmodularComponent{V}Result of structural gauge-submodularity recognition on a candidate residual component, recording original-order variables::Vector{V}, internal indices::Vector{Int}, whether the subset has no free external neighbors (is_closed::Bool), whether a consistent spin gauge makes all active couplings nonpositive (is_submodular::Bool), stop_reason::Symbol (:submodular, :frustrated_cycle, :boundary_coupled, :already_fixed, :zero_scale, :work_limit, or :deadline), the discovered gauge::Vector{Int} ({-1, +1}), and recognition_work::Int.
QUBOPreprocessing.SubmodularCutAttempt — Type
Certified gauge-submodular component cut proof attempt with optional certificate, stop_reason, method, exact normalized component_opt, max_flow, discovered bipartite gauge, complete optimal component assignment, certified fixings, and phase-separated work counters (recognition_work, graph_work, flow_work, verification_work, edge_visits, exact_work).
QUBOPreprocessing.SubmodularCutReport — Type
SubmodularCutReport{V,S}Summary of an optional certified gauge-submodular component cut pass run by apply_submodular_cut!. Retains stop_reason (:applied, :no_persistency, :frustrated_cycle, :boundary_coupled, :already_fixed, :zero_scale, :work_limit, :verification_limit, or :deadline), recognized_components, solved_components, exact normalized component_opt, max_flow, fixed_count, committed fixings::Vector{Pair{V,S}}, and phase-separated work counters (recognition_work, graph_work, flow_work, verification_work, materialization_work, edge_visits, exact_work).
QUBOPreprocessing.SubmodularCutStep — Type
SubmodularCutStepRecorded variable-fixing proof step derived from an exact rational Kolmogorov–Zabih $s$–$t$ min-cut / max-flow pass on a closed gauge-submodular residual component component_variables with certified bipartite spin gauge gauge. Tagged :strong when the variable's cut side is mandatory across all minimum cuts ($u \in \mathcal{R}_S \cup \mathcal{R}_T$), or :weak when allow_weak=true commits a jointly compatible minimum cut across the entire closed component.
QUBOPreprocessing.UpdateReport — Type
UpdateReportAn atomic caller update: stop_reason is :applied, :unchanged, :work_limit or :deadline. edge_visits counts adjacency entries visited, and changed counts caller assumptions added/removed. This is not an inference/proof report.
QUBOPreprocessing.VerificationResult — Type
Read-only verification result: valid, stop_reason and charged term_visits. A budget/deadline stop is not verification success.
QUBOPreprocessing.Workspace — Type
Workspace(model; rules=:identity, integerize_scale::Bool=false, max_decimals::Integer=9, atol::Real=0.0)Privately snapshot a finite Float64 QUBOTools model and its ordered labels. :identity performs no inference; :dominance prepares exact bound caches and a deterministic queue for propagate!. When integerize_scale=true, the snapshot searches $0 \le a, b \le \min(\text{max\_decimals}, 300)$ for the smallest common denominator $m = 2^a \cdot 5^b$ to factor into scale(model) / m via integerize_scale before building exact integer state. With the default atol=0.0, this rescaling is exact (Rational{BigInt}(v) * m must be an integer for every coefficient and offset and Rational{BigInt}(scale(model) / m) * m == Rational{BigInt}(scale(model)), with no rounding); passing atol > 0 opts in to tolerance-based decimal rounding.
ws.max_perturbation::Rational{BigInt} records the largest absolute change in any effective objective coefficient or scaled offset (in objective units, including scale and offset) between the stored snapshot and the input model: $\max_v |\operatorname{Rational\{BigInt\}}(\alpha_{\text{new}}) \cdot \operatorname{Rational\{BigInt\}}(v_{\text{new}}) - \operatorname{Rational\{BigInt\}}(\alpha) \cdot \operatorname{Rational\{BigInt\}}(v)|$ (0 // 1 when the snapshot is exact), and ws.perturbed::Bool is true iff ws.max_perturbation > 0 // 1. Both fields are also recorded on exported certificates (DominanceCertificate / ReductionCertificate) and exports (ExportResult / ConditionedExport).
Explicit caller assumptions and certified deductions have separate provenance and can be rolled back. Source edits never change the snapshot; use reset! to accept a new source. Labels must have stable equality/hash semantics and preserve equality/hash under owned deep copies. Use each workspace serially. Model metadata, solutions and warm starts are outside the objective snapshot.
QUBOPreprocessing.apply_dominance! — Method
apply_dominance!(ws, label; value=nothing, map=nothing, allow_weak=false,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Certify and transactionally commit one unary dominance fixing on ws, recording a DominanceStep on the reversible trail. Returns an UpdateReport.
QUBOPreprocessing.apply_maxcut! — Method
apply_maxcut!(ws, label; value=nothing, map=nothing, allow_weak=false,
max_triangles=typemax(Int), max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)
apply_maxcut!(ws, eliminated, representative; sign=nothing, map=nothing,
allow_weak=false, max_triangles=typemax(Int),
max_fill=typemax(Int), max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)
apply_maxcut!(ws; candidates=nothing, map=nothing, allow_weak=false,
enable_unary=true, enable_pairs=true,
max_triangles=typemax(Int), max_fill=typemax(Int),
max_deductions=typemax(Int), max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)Certify and transactionally commit weighted Max-Cut edge and triangle reductions on the active residual Max-Cut graph $G_{\text{MC}} = (\{0\} \cup F, E_{\text{cut}}, w)$, recording MaxCutStep proof records on the reversible trail and returning a MaxCutReport.
QUBOPreprocessing.apply_probing! — Function
apply_probing!(ws, label, witness=nothing; value=nothing, map=nothing,
max_rounds=1, max_trial_fixes=typemax(Int), double_probe=false,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Certify and transactionally commit one probing fixing on ws by strictly refuting the opposite branch (branch_lower > witness_upper) against the verified parent-scope feasible witness (an original-order vector, label dictionary, Reconstruction, or nothing to synthesize coercive_field_witness), or via witness-free two-branch common-implication probing (:double_probe) when double_probe=true, recording a ProbingStep on the reversible trail. Interrupted or inconclusive probes leave ws at its exact pre-probe checkpoint. Returns an UpdateReport.
QUBOPreprocessing.apply_roof_duality! — Method
apply_roof_duality!(ws; candidates=nothing, map=nothing,
contract_scc=false, witness=nothing, max_fill=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Run an optional certified roof-duality (posiform / implication-network) pass on ws, extracting and transactionally committing strongly persistent variable assignments in candidates (defaulting to all free variables in original order) as RoofDualityStep records on the reversible trail. When contract_scc=true, also extracts and commits 2-SAT pair equivalences from residual implication-network strongly connected components (:roof_scc_pair RelationStep records respecting max_fill). SCC contraction adds a residual SCC decomposition, a closedness scan per SCC and, for each closed residual SCC with K literals, two widest-path passes of O(K²) exact comparisons; verification replays a batch with the same per-SCC passes, and witness-backed contractions also re-validate their witness state per step. deadline_ns is polled at least every 1,024 iterations of the extraction, closedness, widest-path, decomposition and batch-verification loops; the only unpolled steps are two O(k log k) sorts (an SCC's literals and the final contraction order), each followed by a deadline check. max_work counts the SCC decomposition, widest-path and commit work but not the closedness scan. If committing the batch is interrupted by max_work or deadline_ns, the pass rolls back cleanly to the pre-pass checkpoint.
QUBOPreprocessing.apply_submodular_cut! — Method
apply_submodular_cut!(ws; component=nothing, map=nothing, allow_weak=false,
tie_break=:low, max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)
apply_submodular_cut!(ws, component; map=nothing, allow_weak=false,
tie_break=:low, max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)Recognize one or all gauge-submodular residual components in ws, solve each via a direct $(|C| + 2)$-vertex exact $s$-$t$ min-cut, and transactionally commit the resulting strong (allow_weak=false, default) or full minimum-cut (allow_weak=true, selected via tie_break) variable assignments as SubmodularCutStep records on the reversible trail. If committing the batch is interrupted by max_work or deadline_ns, the pass rolls back cleanly to the pre-pass checkpoint. Returns a SubmodularCutReport.
QUBOPreprocessing.apply_weak_batch! — Method
apply_weak_batch!(ws, candidates; map=nothing, atomic=false,
max_work=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Sequentially validate and apply a collection of candidate weak restrictions (label => value pairs or label entries) against the evolving conditioned residual of ws. Because weak persistency is not closed under simultaneous application, each candidate is re-certified after earlier candidates update the residual. When atomic=true, any rejected candidate rolls back the entire batch to its entry checkpoint.
QUBOPreprocessing.assume! — Method
assume!(ws, label, value; map=nothing, max_work=typemax(Int), deadline_ns=nothing)Condition on one explicit original-label assignment, never a certified deduction. When map::DomainGaugeMap is supplied, value is given in map.target_domain and translated bijectively to the original domain. Repeat assignments are no-ops, including a matching certified unary deduction; they do not promote deductions into independent caller assumptions. Conflicts/invalid values throw before mutation. If label was removed by a structural reduction (RelationStep or EliminationStep) or a non-pointwise marginal weak step is active on the trail, assume! never treats the removed variable as freely assignable on the reduced residual; instead it rolls back the reduction suffix and replays retained caller assumptions before imposing the new assumption. A request that previously matched a deduction undone by that rollback is replayed too, as an explicit caller assumption, so the conditioning the caller asked for is not dropped. rollback! discards such requests made after its checkpoint, and unfix! discards those whose deduction it removes.
QUBOPreprocessing.assumptions — Method
assumptions(ws)Return owned original-label/value pairs in application order, O(k) for k active assumptions. No graph scan, residual construction or proof claim is involved.
QUBOPreprocessing.audit_compression — Function
audit_compression(
original,
transformed=nothing;
endpoint::Symbol=:closed,
epsilon::Real=1 // 10,
include_quadratic::Bool=true,
include_negative_quadratic::Bool=false,
chain::Bool=false,
max_vars::Int=12,
max_work::Int=100_000,
) -> CompressionAuditReportExecute a bounded exact coefficient-compression audit comparing original against transformed (or against the candidate model produced by qubolite_compression_candidates when transformed === nothing).
All computations are strictly bounded by max_vars (capped at 16) and max_work; no unbounded exact global solve is ever performed.
QUBOPreprocessing.audit_pipeline! — Method
audit_pipeline!(model_or_ws; rules=:mixed, domain=nothing, gauge=nothing,
residual_state=nothing, exercise_rollback_replay=true,
max_work=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing, kwargs...)Execute and account for all seven preprocessing lifecycle phases (conversion_import, discovery, arithmetic_fallback, verification, export_phase, reconstruction, rollback_replay) under shared max_work, max_exact_work and deadline_ns budgets. Returns (ws, PipelineAccounting).
QUBOPreprocessing.certificate_guarantee — Method
certificate_guarantee(cert::DominanceCertificate)Return the overall guarantee class of cert:
:energy_identitywhencert.stepsis empty,:exact_eliminationwhen every step incert.stepsis anEliminationStep,:optimum_preserving_restrictionwhencert.stepscontains anyDominanceStep,RelationStep,ProbingStep, orRoofDualityStep.
QUBOPreprocessing.changes — Method
changes(ws, checkpoint)Return owned caller assumptions added since a still-valid ancestor checkpoint, in application order; O(number of changes), with no full residual copy.
QUBOPreprocessing.checkpoint — Method
checkpoint(ws) captures a constant-size position without copying the model.
QUBOPreprocessing.coercive_field_ratio — Method
coercive_field_ratio(ws::Workspace; norm::Real=2, map=nothing) -> Float64Return the arithmetic mean of coercive_field_ratios over all currently free variables with at least one active incident coupling (NaN if no free variable has an active coupling).
QUBOPreprocessing.coercive_field_ratios — Method
coercive_field_ratios(ws::Workspace; norm::Real=2, map=nothing) -> Vector{Float64}Return the per-free-variable coercive-field-to-coupling ratios $|h_i| / \|J_{i,\cdot}\|_p$ on the conditioned residual graph of ws in ascending free_variables order. Isolated free variables with $\|J_{i,\cdot}\|_p = 0$ yield 0.0 when $h_i = 0$ and Inf when $h_i \neq 0$.
QUBOPreprocessing.coercive_field_witness — Method
coercive_field_witness(ws::Workspace; polish=true, sequential=true,
max_flips=1000, tie_break=:low, map=nothing) -> Vector{Int}Construct a deterministic parent-scope feasible witness vector for ws by aligning each currently free variable with its conditioned Ising coercive field $h_i$ under sense(ws) (tie_break in (:low, :high) for $h_i = 0$), comparing parallel field alignment against sequential :coercive-ordered conditioned field alignment when sequential=true (breaking $\mathbb{Z}_2$ zero-field tie-break symmetry at the highest-$\ell_1$-coupling anchor when all free fields vanish) with up to max_flips steps of steepest 1-flip local descent on the residual Ising Hamiltonian (polish=true), and lifting the assignment in reverse trail order through all caller assumptions and committed workspace reductions (and through map when provided).
QUBOPreprocessing.coercive_fields — Method
coercive_fields(ws::Workspace; map=nothing) -> Vector{Rational{BigInt}}Return the exact conditioned Ising local fields $h_i$ for all currently free variables in ascending free_variables order. In :bool workspaces, $h_i = \frac{1}{2} L_i + \frac{1}{4} \sum_{j \in \text{free}} Q_{i,j}$; in :spin workspaces, $h_i = L_i$. When a validated DomainGaugeMap is supplied, each field is multiplied by its spin gauge $g_i \in \{-1, +1\}$.
QUBOPreprocessing.compression_counterexamples — Method
compression_counterexamples()Return a named tuple of canonical exact counterexamples and comparison fixtures for Issue #21:
endpoint_tie: 1-variable Boolean model $F(x_1) = x_1 \to F'(x_1) = 0$ at Mücke et al. closed endpoint (endpoint = :closed), where $\operatorname{argmin} F = \{[0]\}$ is retained but $[1] \in \operatorname{argmin} F'$ is introduced as a suboptimal tie.quadratic_endpoint_tie: 2-variable Boolean model $F(x_1, x_2) = -x_1 - x_2 + 3 x_1 x_2$ compressed at:closedto $Q_{12}' = 1$, introducing $[1, 1]$ (original energy $+1 > -1$) into $\operatorname{argmin} F'$.negative_quadratic_lost_optimum: 2-variable Boolean model $F(x_1, x_2) = 2 x_1 + 2 x_2 - 5 x_1 x_2$ where open-interval negative coupling compression (endpoint = :open, $\epsilon = 1//10$, $Q_{12}' = -21//10$) preserves 1-bit flip dominance at $(1, 1)$ but raises $F'(1, 1) = +19//10 > F'(0, 0) = 0$, losing the unique global optimum $[1, 1]$ (relation === :disjoint_optimum_sets).strict_interior_subsumed: 3-variable Boolean model where open-interval compression (endpoint = :open, $\epsilon = 1//2$) preserves $\operatorname{argmin} F' = \operatorname{argmin} F$, but every compressed coefficient belongs to a variable already strictly fixable by unary dominance (#14,prove_dominance), which achieves strictly greater sparsification with an exact constant-shift certificate.max_sense_float_exact::max-sense:spin-domain model with exact binary float coefficients (0.5,1.25,-3.75) audited under exact rational conversion.
QUBOPreprocessing.compression_metrics — Method
compression_metrics(original, transformed) -> CompressionMetricsCompute exact sparsity (nnz_linear, nnz_quadratic) and dynamic-range (max_abs_coeff // min_abs_nonzero) metrics in normalized Boolean minimization form.
QUBOPreprocessing.conditioned_constant — Method
conditioned_constant(ws::Workspace; map=nothing)Return the exact Rational{BigInt} unscaled conditioned constant offset of ws, either in the source domain (map=nothing) or transported through a validated DomainGaugeMap. Spin constants are invariant under spin gauge s_i = g_i t_i and are read in O(1) from the workspace's incremental state.
QUBOPreprocessing.contract_relation! — Method
contract_relation!(ws, eliminated, representative; sign=nothing, map=nothing,
allow_weak=false, enable_probing=false, enable_roof_scc=false,
witness=nothing, max_rounds=1, max_trial_fixes=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Certify and transactionally contract eliminated into representative under $t_{\text{eliminated}} = \sigma t_{\text{representative}}$, recording a RelationStep on the reversible trail and updating surviving fields, degrees and adjacency in $O(\text{touched})$ work. Returns an UpdateReport.
QUBOPreprocessing.contract_relations! — Method
contract_relations!(ws; map=nothing, allow_weak=false,
cascade_dominance=false, allow_weak_dominance=false,
enable_probing=false, enable_roof_scc=false,
witness=nothing, max_rounds=1, max_trial_fixes=typemax(Int),
max_fill=typemax(Int), max_work=typemax(Int),
max_deductions=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Run queue-driven certified pair relation detection and signed contraction on ws without scanning all vertex pairs globally. Candidate active vertices are popped from an incremental relation queue and their active incident edges (plus exact non-adjacent twins when allow_weak=true) are tested for certified pair equivalences or implications (:interval, :exact, :glk_pair or :coflip_pair), with optional two-branch probing pair equivalences (enable_probing=true, :probing_pair) and roof-duality residual-SCC 2-SAT pair equivalences (enable_roof_scc=true, :roof_scc_pair). Contractions that would introduce more than max_fill new fill edges on the representative are skipped. When cascade_dominance=true (requiring Workspace(model; rules=:dominance), rules=:elimination, rules=:relations or rules=:mixed), dirty unary dominance candidates are interleaved with relation contractions. Returns a PropagationReport.
QUBOPreprocessing.deductions — Method
deductions(ws; since=nothing)Return owned original-label/value pairs for certified constant-fixing deductions, optionally added after a valid ancestor checkpoint. Scan only fixing records in that range; queue-only history and the source graph are not scanned. Caller assumptions remain available separately through assumptions/changes, and structural reductions (RelationStep, EliminationStep) are included in reductions.
QUBOPreprocessing.degree — Method
degree(ws::Workspace, label)Return the number of remaining nonzero quadratic interactions incident to label among currently free variables, in O(1). Fixed variables have degree 0. Stored zero quadratic entries do not count toward degree, and linear fields are tracked separately via effective_field.
QUBOPreprocessing.domain_map — Method
domain_map(ws; domain=..., gauge=nothing)Construct a checked DomainGaugeMap tied to ws and its current generation. domain must be :bool or :spin (defaulting to the workspace's source domain). gauge may be nothing (all +1), a one-based vector of ±1 in original variable order, or a dictionary of label => ±1 entries. Constructing a map validates and copies original label metadata in O(n) without performing a whole-model quadratic matrix cast (or O(n+m) once when precomputing the root constant offset for a non-identity binary gauge).
QUBOPreprocessing.effective_field — Method
effective_field(ws::Workspace, label; map=nothing)Return the exact Rational{BigInt} conditioned linear/field coefficient for a currently free original label, either in the workspace's source domain (map=nothing) or transported through a validated DomainGaugeMap. Requires no whole-model cast (O(1) in spin coordinates and identity-gauge binary coordinates; O(degree) in gauged binary coordinates).
QUBOPreprocessing.eliminate_block! — Method
eliminate_block!(ws, block_labels; map=nothing, tie_break=:low,
max_block_size=12, max_separator=2, max_fill=typemax(Int),
require_unique=false, max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)Certify and transactionally eliminate a connected active block block_labels of size 2 <= |B| <= max_block_size across its external active separator $S = N(B)$ of size 0 <= |S| <= max_separator <= 2, recording a batch of |B| EliminationSteps on the reversible trail and updating surviving separator fields, fill edges and degrees. Returns an UpdateReport with changed == |B| when applied.
QUBOPreprocessing.eliminate_low_degree! — Method
eliminate_low_degree!(ws; map=nothing, max_degree=2, max_fill=typemax(Int),
tie_break=:low, cascade_dominance=false,
allow_weak_dominance=false, enable_blocks=false,
max_block_size=12, max_separator=2,
require_unique_blocks=false, max_work=typemax(Int),
max_deductions=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Run queue-driven exact local elimination for free vertices of active degree 0 <= degree(ws, label) <= max_degree (default max_degree=2; max_degree=3 enables guarded degree-three Ising reduction whenever the local conditional minimum has zero cubic Fourier coefficient α_123 = 0) without scanning the whole graph per elimination. Eliminations that would introduce more than max_fill new fill edges are skipped and deferred. When enable_blocks=true, also discovers and eliminates connected active vertex blocks 2 <= |B| <= max_block_size separated from the rest of the active graph by a boundary 0 <= |N(B)| <= max_separator <= 2 (0-separator small components, 1-separator articulation-point pendant blocks, and 2-separator biconnected blocks). When cascade_dominance=true (requiring Workspace(model; rules=:dominance), rules=:elimination, rules=:relations or rules=:mixed), dirty dominance candidates are interleaved with low-degree eliminations so dominance fixings that drop neighbor degrees to <= max_degree and local eliminations that strengthen neighbor derivative bounds cascade automatically. Returns a PropagationReport.
QUBOPreprocessing.eliminate_variable! — Method
eliminate_variable!(ws, label; map=nothing, tie_break=:low, max_degree=2,
max_work=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Certify and transactionally eliminate a free variable of active degree 0..max_degree (default max_degree=2) from ws, recording an EliminationStep with its exact argmin reconstruction table and updating surviving neighbor fields, fill edges and degrees on the reversible trail. Higher-degree variables are refused with :degree_too_high. When a collection of labels is passed, delegates to eliminate_block!. Returns an UpdateReport.
QUBOPreprocessing.export_certificate — Method
export_certificate(ws; map=nothing)Explicitly capture the complete owned reduction chain and caller scope (optionally transported into map::DomainGaugeMap), or return nothing in constant-size work if no certified reduction exists. Verify with verify_certificate; applicability requires the captured current trail tip. No inference, solver dispatch or residual materialization occurs here.
QUBOPreprocessing.export_model — Method
export_model(result)Return a fresh QUBOTools model with exactly the captured stored objective and ordered labels. Each call owns all mutable data. Editing this model does not edit the export certificate or the historical source used by reconstruction.
QUBOPreprocessing.generation — Method
generation(ws_or_export) returns its immutable source/workspace identity.
QUBOPreprocessing.incident_couplings — Method
incident_couplings(ws::Workspace, label; map=nothing)Return owned neighbor_label => Rational{BigInt} pairs for remaining nonzero interactions incident to a currently free label, either in the source domain (map=nothing) or transported through a validated DomainGaugeMap. Costs O(source degree) without scanning the rest of the graph.
QUBOPreprocessing.index_map — Method
index_map(ws_or_export) returns an owned original-index → residual-index vector.
QUBOPreprocessing.integerize_scale — Method
integerize_scale(model; max_decimals::Integer=9, atol::Real=0.0)Return an owned copy of model where the smallest multiplier $m = 2^a \cdot 5^b$ in the bounded search range $0 \le a, b \le \min(\text{max\_decimals}, 300)$ (with $m \le 2^{53}$ and all scaled integers $|r| \le 2^{53}$) that scales all linear coefficients, quadratic coefficients, and offset to integers is factored into scale(model) / m.
By default (atol=0.0), the rescaled snapshot is exact: a multiplier $m$ is accepted only when Rational{BigInt}(v) * m is an exact integer for every coefficient and offset and Rational{BigInt}(scale(model) / m) * m == Rational{BigInt}(scale(model)), using no tolerance and no rounding (multiplying binary64 by $2^a$ is exact). Only exact dyadic powers ($b = 0$, $0 \le a \le \text{max\_decimals}$) are considered under atol=0.0; coefficients whose binary64 denominator exceeds $2^{\text{max\_decimals}}$ (such as binary64 approximations of 0.1, 0.3, 0.9 under the default max_decimals=9) remain unchanged.
Passing atol > 0 explicitly opts in to tolerance-based decimal multipliers ($b \ge 1$), accepting irreducible $(a, b)$ when every non-zero coefficient and offset satisfies abs(Rational{BigInt}(v) * m - r) <= Rational{BigInt}(Float64(atol)) * abs(r) in exact rational arithmetic. When the accepted multiplier changes any effective objective term $\operatorname{Rational\{BigInt\}}(\alpha_{\text{new}}) \cdot r \ne \operatorname{Rational\{BigInt\}}(\alpha) \cdot \operatorname{Rational\{BigInt\}}(v)$, the rescaled model is a perturbed approximation of model.
QUBOPreprocessing.is_gauge_invariant — Method
is_gauge_invariant(ws::Workspace; atol::Real=0//1, map=nothing) -> BoolReturn true iff every currently free variable in ws satisfies $|h_i| \le \text{atol}$ (so the conditioned residual Ising Hamiltonian is $\mathbb{Z}_2$ spin-flip invariant up to atol).
QUBOPreprocessing.is_integer_scaled — Method
is_integer_scaled(model_or_workspace)::BoolReturn true iff every linear coefficient, quadratic coefficient, and constant offset of model_or_workspace is a finite exact integer (with arbitrary finite model scale). On a Workspace, checks the currently conditioned residual objective (conditioned_constant, effective_field, and incident_couplings over all free variables).
QUBOPreprocessing.lift_state — Method
lift_state(map::DomainGaugeMap, state::AbstractVector)Bijectively lift a complete original-order state vector from map.target_domain back into map.source_domain under map.gauge. Returns an owned Vector{Int}.
QUBOPreprocessing.lift_value — Method
lift_value(map::DomainGaugeMap, label, value)Lift one target-domain assignment value for label back into map.source_domain under map.gauge (s_i = g_i t_i, x_i = (s_i + 1)/2).
QUBOPreprocessing.map_state — Method
map_state(map::DomainGaugeMap, state::AbstractVector)Bijectively map a complete original-order state vector from map.source_domain into map.target_domain under map.gauge. Returns an owned Vector{Int}.
QUBOPreprocessing.map_value — Method
map_value(map::DomainGaugeMap, label, value)Map one original-domain assignment value for label into map.target_domain under map.gauge (x_i = (s_i + 1)/2, s_i = g_i t_i).
QUBOPreprocessing.materialize — Method
materialize(ws; coefficient_type=Float64, rounding=:none, normalization=:none, map=nothing)
materialize(ws, map::DomainGaugeMap; coefficient_type=Float64, rounding=:none, normalization=:none)Explicitly capture an owned export. With default normalization and without fixings or a coordinate map, this is the Float64 identity export (certificate.unchanged_representation == !ws.perturbed). With caller assumptions, certified deductions or a DomainGaugeMap, return a ConditionedExport with the complete proof chain when present: Float64 transport must represent every conditioned/converted coefficient and constant exactly, or the call raises ArgumentError; use coefficient_type=Rational{BigInt} for exact transport. Materialization scans/copies the graph; it is never implicit in updates.
With coefficient_type=Float64, opt in to rounding=:nearest to round each residual linear/quadratic coefficient and constant to its nearest finite Float64. If any coefficient changes, the export has status=:rounded, certificate.unchanged_representation=false, and perturbed=true when the effective coefficient change is nonzero (a zero scale makes it zero). max_perturbation is the maximum of the existing input perturbation and abs(scale) * abs(rounded - exact) over the residual coefficients and constant, computed exactly as Rational{BigInt} in original objective units. It is a coefficient bound, not an objective-error or optimality certificate. The reduction proof still describes the exact residual; reconstruction uses the historical source objective rather than the rounded solver objective. The scale is never rounded, and a nonfinite rounded coefficient still raises ArgumentError.
With coefficient_type=Float64 and rounding=:none, normalization=:integer factors all mapped coefficients, including the constant, into primitive integers and a common positive rational factor absorbed into the scale. Every integer and the adjusted scale must be exactly representable as finite Float64; otherwise the call raises ArgumentError. An all-zero residual uses factor one and retains the source scale. Exact normalization adds no perturbation, preserves the historical source and proof, and sets unchanged_representation=false when the factor is not one. The default normalization=:none retains the stored coefficients/scale.
QUBOPreprocessing.maxcut_cut_weight — Method
maxcut_cut_weight(mc::MaxCutGraph, cut_side)Evaluate the exact rational cut weight $\operatorname{CutWeight}(z) = \sum_{(a, b) \in E_{\text{cut}}} w_{ab} \, \delta(z_a \ne z_b)$ for a cut assignment cut_side ({-1, +1} vector of length length(mc.variables) with implicit z_0 = +1, vector of length length(mc.variables) + 1 starting with z_0, or dictionary mapping active labels and optionally 0 / :reference to {-1, +1}).
QUBOPreprocessing.maxcut_energy — Method
maxcut_energy(mc::MaxCutGraph, cut_side; scaled=false)Evaluate the exact normalized active spin energy $\tilde{F}(z) = C_{\text{cut}} - \operatorname{CutWeight}(z)$ (or scaled by mc.scale when scaled=true).
QUBOPreprocessing.maxcut_graph — Method
maxcut_graph(ws; map=nothing, max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Construct an owned MaxCutGraph representing the active residual of ws as a signed weighted Max-Cut instance on $\{0\} \cup F$ with explicit reference vertex 0.
QUBOPreprocessing.maxcut_to_spin — Method
maxcut_to_spin(mc::MaxCutGraph, cut_side; mapped=false)Project a cut assignment cut_side on $\{0\} \cup F$ to an ordered spin vector $s_u = g_u z_0 z_u \in \{-1, +1\}$ in original canonical spin coordinates (or gauged spin coordinates $t_u = z_0 z_u$ when mapped=true). Invariant under global cut reversal $z \mapsto -z$.
QUBOPreprocessing.original_variables — Method
original_variables(ws_or_export) returns owned labels in original index order.
QUBOPreprocessing.persistency — Method
persistency(step_or_certificate)Return :strong when a step, map, or certificate preserves all optima on its scope, or :weak when any step relies on tie-breaking / weak persistency.
QUBOPreprocessing.preprocess — Method
preprocess(model; rules=:identity, integerize_scale::Bool=(rules !== :identity), max_decimals::Integer=9, atol::Real=0.0, time_limit=nothing, kwargs...)Return (workspace, report) using the same snapshot path as Workspace. :identity returns a no-inference IdentityReport; :dominance runs propagate! with forwarded keyword limits and returns its report. With rules=:mixed and a time_limit in seconds, every reduction family runs under that budget through schedule_budgeted! (forwarding its keywords) and its BudgetedScheduleReport is returned (the budget starts once the workspace is built, and the cheap rules' capped floor can run past it); without time_limit, :mixed runs schedule_reductions!. When rules !== :identity, integerize_scale defaults to true with atol=0.0, so only exact dyadic denominators $2^a$ within 0 <= a <= max_decimals are factored into scale before reduction (ws.perturbed == false, ws.max_perturbation == 0 // 1). Passing atol > 0 explicitly opts in to tolerance-based decimal rounding and records any resulting effective-coefficient or scaled-offset perturbation on ws and its exported certificates. No model is materialized implicitly.
QUBOPreprocessing.probe_variables! — Function
probe_variables!(ws, witness=nothing; candidates=nothing, order=:index,
map=nothing, max_candidates=typemax(Int), max_rounds=1,
max_trial_fixes=typemax(Int), double_probe=false,
contract_relations=false, max_fill=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Run an optional bounded certified probing pass across candidates (defaulting to all currently free variables) using a verified parent-scope feasible witness (or synthesizing coercive_field_witness when witness === nothing). Candidate order is controlled by order in (:index, :coercive, :extremal). Each candidate temporarily conditions on the opposite assignment, propagates bounded trial dominance, and commits a ProbingStep when the trial branch lower bound strictly refutes the branch against witness. When double_probe=true or contract_relations=true, unrefuted candidates also compare both trial branches (low and high) to commit common unary fixings (:double_probe ProbingStep) and/or opposite-branch 2-SAT pair contractions (:probing_pair RelationStep respecting max_fill). Cancelled or inconclusive trial probes roll back cleanly to the pre-probe checkpoint while charging executed work in the returned ProbingReport.
QUBOPreprocessing.propagate! — Method
propagate!(ws; map=nothing, allow_weak=false, max_work=typemax(Int),
max_deductions=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Run deterministic dominance propagation on a workspace selected with rules=:dominance, optionally validating and operating through a DomainGaugeMap. By default (allow_weak=false), only strong strict dominance is applied (:strong persistency). When allow_weak=true, weak optimum-preserving restrictions are also applied sequentially on the evolving residual so later candidates are always re-evaluated against already-applied steps.
QUBOPreprocessing.prove_dominance — Method
prove_dominance(ws, label; map=nothing, allow_weak=false, value=nothing,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Prove one unary dominance restriction without changing the workspace, optionally operating in the coordinate system of map::DomainGaugeMap or allowing a weak optimum-preserving restriction (allow_weak=true). By default (allow_weak=false), only strong strict-dominance steps are proved.
QUBOPreprocessing.prove_elimination — Method
prove_elimination(ws, label; map=nothing, tie_break=:low, max_degree=2,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)
prove_elimination(ws, block_labels; map=nothing, tie_break=:low,
max_block_size=12, max_separator=2, require_unique=false,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Prove an exact bounded-degree (0 <= degree(ws, label) <= max_degree) local variable elimination or a bounded-separator (0 <= |N(B)| <= max_separator <= 2, 2 <= |B| <= max_block_size) connected block elimination without mutating ws. By default (max_degree=2), only isolated, leaf and degree-two single variables are eligible; higher-degree variables are refused with :degree_too_high. When max_degree=3 is explicitly requested, guarded zero-cubic-Fourier degree-three reduction (alpha_123 == 0) is enabled, covering zero-field star–triangle elimination as well as nonzero-field degree-3 vertices whose conditional minimum over the $2^3 = 8$ neighbor states is an exact quadratic polynomial; degree-3 variables whose exact marginal has a nonzero cubic interaction (alpha_123 != 0) are refused with :nonquadratic_elimination. When a collection block_labels of at least 2 active variables is supplied, proves a batch of |B| EliminationSteps across the external separator $S = N(B)$ (|S| <= 2).
QUBOPreprocessing.prove_maxcut — Method
prove_maxcut(ws, label; map=nothing, allow_weak=false, value=nothing,
max_triangles=typemax(Int), max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)
prove_maxcut(ws, eliminated, representative; sign=nothing, map=nothing,
allow_weak=false, max_triangles=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Prove a certified weighted Max-Cut edge or triangle preprocessing restriction on the active residual Max-Cut graph $G_{\text{MC}} = (\{0\} \cup F, E_{\text{cut}}, w)$ without mutating ws. With (ws, label), tests a unary variable fixing (representative == 0) using the reference edge $(u, 0)$ and bounded field-coupling triangles $\{u, 0, c\}$. With (ws, eliminated, representative), tests a signed pair contraction $t_{\text{eliminated}} = \sigma t_{\text{representative}}$ using the internal edge $(u, v)$ and bounded triangles $\{u, v, c\}$ (including $c = 0$ and $c \in F \setminus \{u, v\}$). Returns a MaxCutAttempt.
QUBOPreprocessing.prove_probing — Function
prove_probing(ws, label, witness=nothing; map=nothing, value=nothing,
double_probe=false, max_rounds=1, max_trial_fixes=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Prove one certified probing restriction label => value without mutating ws by temporarily conditioning on the opposite branch, propagating bounded trial unary dominance (max_rounds, max_trial_fixes), and strictly refuting the branch lower bound (branch_lower > witness_upper) against the verified parent-scope feasible witness (an original-order vector, label dictionary, Reconstruction, or nothing to synthesize coercive_field_witness). When double_probe=true, also checks whether both branches of a neighboring variable deduce label => value (:double_probe). All trial mutations are rolled back before returning.
QUBOPreprocessing.prove_relation — Method
prove_relation(ws, eliminated, representative; sign=nothing, map=nothing,
allow_weak=false, enable_probing=false, enable_roof_scc=false,
witness=nothing, max_rounds=1, max_trial_fixes=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Prove a signed pair relation $t_{\text{eliminated}} = \sigma t_{\text{representative}}$ without mutating ws. When sign is omitted, the candidate sign opposing the effective coupling between eliminated and representative is tested. When enable_probing=true, 2-SAT trial probing cascades (:probing_pair) are also tested. When enable_roof_scc=true, roof-duality implication-network residual SCC equivalences (:roof_scc_pair) are also tested.
QUBOPreprocessing.prove_roof_duality — Method
prove_roof_duality(ws; candidates=nothing, map=nothing,
contract_scc=false, witness=nothing, max_fill=typemax(Int),
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)
prove_roof_duality(ws, label; map=nothing, value=nothing,
max_work=typemax(Int), max_exact_work=typemax(Int), deadline_ns=nothing)Compute the exact rational implication-network (posiform / roof-duality) lower bound and extract strongly persistent variable assignments without mutating ws. When contract_scc=true, also extracts strongly persistent signed pair contractions from nontrivial residual SCCs (:roof_scc_pair). SCC contraction adds a residual SCC decomposition, a closedness scan per SCC and, for each closed residual SCC with K literals, two widest-path passes of O(K²) exact comparisons; verification replays a batch with the same per-SCC passes, and witness-backed contractions also re-validate their witness state per step. deadline_ns is polled at least every 1,024 iterations of the extraction, closedness, widest-path, decomposition and batch-verification loops; the only unpolled steps are two O(k log k) sorts (an SCC's literals and the final contraction order), each followed by a deadline check. max_work counts the SCC decomposition, widest-path and commit work but not the closedness scan. Returns a RoofDualityAttempt containing the exact normalized lower_bound, scaled model objective_bound, maximum S-T flow max_flow, strongly persistent fixings, contracted_count, contractions, phase-separated work counters, and (when at least one reduction is proved) a locally verifiable DominanceCertificate.
QUBOPreprocessing.prove_submodular_cut — Method
prove_submodular_cut(ws; component=nothing, map=nothing, allow_weak=false,
tie_break=:low, max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)
prove_submodular_cut(ws, component_or_label; map=nothing, allow_weak=false,
tie_break=:low, value=nothing, max_work=typemax(Int),
max_exact_work=typemax(Int), deadline_ns=nothing)Recognize one or all gauge-submodular residual components in ws and solve them via a direct $(|C| + 2)$-vertex exact $s$-$t$ min-cut without mutating ws. By default (allow_weak=false), only strongly persistent assignments (optimal in every minimum cut of the component) are certified. When allow_weak=true, a complete jointly optimal component assignment is selected via tie_break (:low, :high, :source, or :sink), tagging tied vertices with :weak persistency. Returns a SubmodularCutAttempt.
QUBOPreprocessing.qubolite_compression_candidates — Method
qubolite_compression_candidates(
model_or_ws;
endpoint::Symbol=:closed,
epsilon::Real=1 // 10,
include_quadratic::Bool=true,
include_negative_quadratic::Bool=false,
chain::Bool=false,
max_work::Int=10_000,
)Evaluate the Mücke–Gerlach–Piatkowski (2023) Theorem 2 / qubolite dynamic-range compression rule on exact rationalized coefficients without performing any global solve.
Arguments:
endpoint::closed($\tau = 0$, setting coefficients to the exact equality threshold where $\Delta_i = 0$, which proves only $\operatorname{opt}(F) \subseteq \operatorname{opt}(F')$ and can introduce suboptimal ties) or:open($\tau = \epsilon > 0$, retaining strict sign).epsilon: positive interior margin $\epsilon > 0$ used whenendpoint === :open.include_quadratic: whether to evaluate off-diagonal $Q_{ij}$ updates in addition to diagonal $L_i$ updates.include_negative_quadratic: whether to include negative coupling compression ($Q_{ij} < 0 \mapsto Q_{ij}' > Q_{ij}$ when $L_a + c_{a,-b}^+ + Q_{ij} \le -\tau$), which can lose all original global optima even whenendpoint === :open.chain: iftrue, apply each candidate immediately toL/Qbefore evaluating later entries; iffalse, compute all candidates against the initial polynomial and apply them as a batch.max_work: strict work cap on coefficient/incidence inspections (stop_reason === :work_limit_exceededif exceeded).
Returns a named tuple (candidates, transformed_model, bound_work, stop_reason).
QUBOPreprocessing.recognize_submodular_component — Method
recognize_submodular_component(ws, component; max_work=typemax(Int), deadline_ns=nothing)Check whether component (an iterable of original variable labels) is a closed active residual component (no free external neighbors with nonzero coupling) and whether a spin gauge $\sigma_u \in \{-1, +1\}$ makes every active coupling in component nonpositive ($\sigma_u \sigma_v \tilde{J}_{uv} \le 0$). Returns a SubmodularComponent without constructing a flow network.
QUBOPreprocessing.recognize_submodular_components — Method
recognize_submodular_components(ws; max_work=typemax(Int), deadline_ns=nothing)Partition all currently free variables in ws into connected residual components and test each component for gauge-submodularity via bipartite edge-parity BFS. Returns (components::Vector{SubmodularComponent{V}}, stop_reason::Symbol, recognition_work::Int).
QUBOPreprocessing.reconstruct — Function
reconstruct(result, y)Validate a complete one-based residual-domain vector (matching the original domain for unmapped exports, or map.target_domain when materialized through a DomainGaugeMap) and return an owned state in original-variable order and original domain together with an ordinary Float64 original-energy evaluation. Reject missing, partial, non-real, nonfinite and out-of-domain values. Numerical overflow is reported in energy.finite; neither the energy nor this reconstruction certifies optimality.
QUBOPreprocessing.reductions — Method
reductions(ws; since=nothing)Return owned proof records (DominanceStep, RelationStep, EliminationStep, ProbingStep) in application order for all certified reductions committed on ws, optionally added after a valid ancestor checkpoint since.
QUBOPreprocessing.relation_map — Method
relation_map(ws; map=nothing)
relation_map(ws, label; map=nothing)Read-only query returning the current representative label and relative parity sign (rep_label => sign with sign in (-1, 1)) induced by active RelationStep contractions on ws, without mutating or path-compressing trail state during exploratory branches. With one argument ws, returns an owned Vector{Pair{V,Int}} in original variable order; with (ws, label), resolves a single original variable in $O(\text{chain depth})$ work. When map::DomainGaugeMap is supplied, the parity sign is expressed in map's gauged coordinate system.
QUBOPreprocessing.reset! — Method
reset!(ws, model; integerize_scale::Bool=false, max_decimals::Integer=9, atol::Real=0.0)Validate a fresh snapshot before committing it. Failed validation preserves the old workspace. Success creates a fresh generation, including for an identical source. Owned exports remain evidence for their historical generation. With default atol=0.0, integerize_scale=true is exact (ws.perturbed == false, ws.max_perturbation == 0 // 1); passing atol > 0 opts in to tolerance-based decimal rounding and updates ws.perturbed and ws.max_perturbation from the stored scale and coefficients/offset.
QUBOPreprocessing.rollback! — Method
rollback!(ws, checkpoint; report=false)Restore fields, constant, free/fixed values, queue flags and assumptions exactly in reverse trail order. Cost is proportional to undone entries/touched fields and appended queue entries. No source graph copy or floating subtraction occurs. Invalid checkpoints fail before mutation. Rollback completes without a work or deadline limit; callers bound its cost by bounding preceding updates.
By default return ws. With report=true, return a RollbackReport whose removed-fixing vectors are prepared before mutation. Capture visits only fixing records after cp, not queue-only history or unrelated source vertices. Rollback itself still costs all undone journal/field/queue work. Empty reports cost constant-size work and no full materialization is needed.
QUBOPreprocessing.sample_preprocessed — Function
sample_preprocessed(model_or_workspace, fresh_child_factory; kwargs...)Optional direct consumer, available after loading QUBODrivers 0.6.5 or later. Use an existing workspace or construct one with rules=:dominance (the model default) / :identity. Explicitly capture a Float64-safe residual, verify its proof chain, invoke a fresh Float64 QUBODrivers child, validate complete states, and recompute original energies with one shared source evaluator per call. All-fixed cases run locally. Return a SolverResult.
Supported keywords include max_work, max_deductions, max_exact_work, absolute deadline_ns, max_child_variables=16, max_results=1024, child_work_bound=nothing, min_reduction=0 and max_prep_fraction=1. With min_reduction > 0, the child solves the original model instead of the residual when preprocessing removed less than that fraction of the variables; with max_prep_fraction < 1 and a deadline_ns, it does so when setup and propagation used more than that fraction of the time to the deadline (checked before the residual is built). The fallback's identity rebuild is charged to max_work. Neither applies with caller assumptions or when every variable was removed. metadata.child_model (:residual/:original) and metadata.bypass_reason record the choice. Work is one shared allowance for charged adapter storage/update/verification/reconstruction units and a reserved child bound. The built-in ExactSampler has a conservative bound; another finite-work child requires a supplied (child, residual, remaining_work, deadline_ns) -> nonnegative Int bound that the child honors, otherwise dispatch abstains. Deadline checks surround noninterruptible copy boundaries; remaining seconds are passed through MOI.TimeLimitSec when supported. A child is responsible for honoring its declared bounds/deadline. There is no hard real-time/process-preemption guarantee.
Unsafe Float64 transport abstains before child dispatch. Exact residuals remain available through the core materialization API. Valid heuristic/interrupted child states do not gain optimality from certified preprocessing. The child's public MOI.OPTIMAL is retained only for a verified complete chain, validated result1, finite original energy and unexpired allowance. Caller scopes remain qualified. Sampling distributions and physical-read semantics are not preserved.
QUBOPreprocessing.schedule! — Method
schedule!(ws; policy=:legacy_benchmark, allow_weak=false, time_limit=nothing,
input_edges=nothing, kwargs...)Package-owned explicit policy dispatch. :legacy_benchmark preserves the single historical benchmark sequence, :legacy_middle lifts its flow/block/relation gates but retains the probing gate, and :legacy_census preserves the separate historical census loop of up to eight rounds. These return :policy_complete, not an all-family fixpoint claim. Dimensions are the workspace's original graph; input_edges can retain a source representation's edge count including explicit zero terms (the historical benchmark used length(raw.Q)).
:cheap runs dominance and low-degree elimination only and returns :cheap_quiescent on completion. Relations, star-triangle, blocks, flow, Max-Cut and probing are explicitly skipped. This makes no expensive-family quiescence or performance claim.
:budgeted requires time_limit and forwards its other options to schedule_budgeted!, whose defaults are unchanged. Time limits are rejected for the untimed legacy/cheap policies instead of silently ignored. No policy implies a recommended default replacement for a measured workload.
QUBOPreprocessing.schedule_budgeted! — Method
schedule_budgeted!(ws; time_limit, allow_weak=false, enable_probing=true,
max_block_size=12, probe_rounds=8, guaranteed_relation_work=75_000,
tie_break=:low, double_probe=false, contract_relations=false,
on_family=nothing)Run every certified reduction family on ws under one wall-clock budget of time_limit seconds, instead of caller-chosen size gates. The budget counts from this call; building ws (snapshot import and integerization) happens before it starts.
The cheap rules (dominance, low-degree and star-triangle elimination, pair relations: schedule_reductions!) first reach a fixpoint whatever the budget, with pair-relation search limited to guaranteed_relation_work work units. So a small budget never does less than this floor, while relation search cannot run for minutes on a dense model. time_limit is therefore a soft cutoff: the floor can run past it. Within the budget, the cheap rules continue without the relation limit, and the expensive families run in turn — roof duality, submodular cuts, Max-Cut, block elimination (max_block_size), residual-SCC contraction and, when enable_probing, coercive-order probing with probe_rounds trial rounds. Each of these gets an equal share of the budget still left, so one slow family cannot consume it all and time a fast family leaves passes to the next. The cheap rules run again, with the next family's share, after every expensive family that removes a variable. Passes repeat while some family has not finished on the current workspace: a family runs again when its share ran out before it finished, or when variables were removed after its last run. Every budgeted call shares the deadline, so the schedule returns within a small margin of time_limit or of the end of the cheap floor, whichever is later, and an interrupted call rolls back cleanly. On large dense models, garbage collection of exact-arithmetic temporaries can still stretch a call past its share.
allow_weak=true additionally applies weak dominance, weak relations and weak submodular/Max-Cut reductions, which keep at least one optimum; exact elimination may resolve ties in either mode. Returns a BudgetedScheduleReport with per-family time and removed variables.
double_probe and contract_relations opt into the corresponding probing operations; both default to false, preserving the original budgeted policy. An optional on_family(event) function observes every completed family call. The event includes family, time_s, freed, stop_reason, and public before_checkpoint/after_checkpoint values. Callback time consumes the shared scheduling budget but is excluded from the family's own time. Callback exceptions propagate; already completed deductions are not rolled back. The callback must not mutate the workspace. The default performs no callback/checkpoint work.
QUBOPreprocessing.schedule_reductions! — Method
schedule_reductions!(ws; map=nothing, enable_dominance=true,
enable_elimination=true, enable_relations=true,
enable_star_triangle=false, enable_blocks=false,
max_block_size=12, max_separator=2,
require_unique_blocks=false, allow_weak_dominance=false,
allow_weak_relations=false, allow_exact_fallback=true,
stop_on_disabled_optional=false, tie_break=:low,
max_fill=typemax(Int), max_total_fill=typemax(Int),
relation_work_budget=typemax(Int), max_work=typemax(Int),
max_deductions=typemax(Int), max_exact_work=typemax(Int),
deadline_ns=nothing)Run a deterministic mixed exact reduction schedule on one shared Workspace and Generation without alternating full QUBO↔Ising materializations. Cheap dirty-neighborhood unary propagation (:dominance) and degree-<= 2 local elimination (:elimination) run first; heavier passes (:star_triangle at degree 3, disabled by default, :relations bounded by relation_work_budget and max_fill / max_total_fill, and :block_elimination when enable_blocks=true) run only when cheap passes are quiescent, and immediately cascade back to cheap passes whenever a reduction dirties a local neighborhood. Returns a ScheduleReport.
QUBOPreprocessing.spin_to_maxcut — Method
spin_to_maxcut(mc::MaxCutGraph, spin_state; reference_side=1, mapped=false)Embed an active spin state spin_state ({-1, +1} vector or label dictionary) into a cut-side vector [z_0, z_1, ..., z_k] on $\{0\} \cup F$ with z_0 == reference_side (-1 or +1).
QUBOPreprocessing.step_guarantee — Method
step_guarantee(step_or_map)Return the algebraic guarantee class of a preprocessing step or coordinate map:
:energy_identityforDomainGaugeMap,:exact_eliminationforEliminationStep,:optimum_preserving_restrictionforDominanceStep,RelationStep,ProbingStep,RoofDualityStep,SubmodularCutStep, andMaxCutStep.
QUBOPreprocessing.transport_certificate — Method
transport_certificate(ws::Workspace, cert::DominanceCertificate, map::DomainGaugeMap)Transport a valid DominanceCertificate for ws into the coordinate representation of map while preserving its generation, branch checkpoint, explicit caller assumptions and lifted original-domain deductions/reductions. Rejects stale generations, mismatched source/variable ordering, invalid gauges or stale branch scopes with ArgumentError.
QUBOPreprocessing.trivial_dominance_fraction — Method
trivial_dominance_fraction(ws::Workspace; atol::Real=0//1, map=nothing) -> Float64Return the fraction of currently free variables in ws whose conditioned Ising local field strictly dominates its incident coupling $\ell_1$ norm by more than atol ($|h_i| > \sum_{j \in N(i)} |J_{i,j}| + \text{atol}$; NaN when free_count(ws) == 0).
QUBOPreprocessing.unfix! — Method
unfix!(ws, label; max_work=typemax(Int), deadline_ns=nothing)Remove a caller assumption. The most recent one rolls back locally. Otherwise build fresh algebra and replay all retained assumptions, then replace state only on success; every prior checkpoint is invalidated. This conservative path costs O(n+m + retained adjacency work), plus exact arithmetic, and allocates a new workspace state. max_work bounds replay adjacency visits, not initialization; the latter always costs O(n+m). Deadline/work stops preserve the old state. Later deductions are undone by the local path. Non-LIFO replay discards all deductions and replays only explicit caller assumptions, never inferred values. Resume inference explicitly with propagate!. Removing a deduction directly is rejected; use its ancestor checkpoint.
QUBOPreprocessing.verify_certificate — Method
verify_certificate(ws, certificate; map=nothing, max_work=typemax(Int), deadline_ns=nothing)Independently recheck source identity, current caller scope, optional DomainGaugeMap provenance and the complete ordered reduction chain (DominanceStep, RelationStep, EliminationStep, ProbingStep, RoofDualityStep, SubmodularCutStep, MaxCutStep) using exact original-coefficient evolution and domain/gauge conversion. Never trust cached workspace fields or an authenticated identifier alone.
QUBOPreprocessing.zero_field_fraction — Method
zero_field_fraction(ws::Workspace; atol::Real=0//1, map=nothing) -> Float64Return the fraction of currently free variables in ws whose conditioned Ising local field satisfies $|h_i| \le \text{atol}$ (NaN when free_count(ws) == 0).