Use preprocessing in a solver workflow
Preprocessing sits between your model and your solver. It can remove variables whose values are proved to hold in every optimum, then restore those variables after the solver returns a state for the smaller problem. Such a proved fixing is a deduction. An assumption is a value you choose, for example to explore one branch of a search; deductions made under that assumption apply within that branch. If your algorithm repeatedly changes assumptions, you can keep the same workspace and undo a branch before trying the next one.
This guide starts with a complete core-only solve. It then reuses a workspace across two branches and finishes with the optional solver adapters. The model reference collects the input, ownership and numerical contracts used throughout.
Choose the path that matches your task:
- For one model and a solver of your choice, follow the complete solve below.
- For repeated branch decisions on the same model, continue with workspace reuse.
- To let an adapter manage the solve and reconstruction, use the direct QUBODrivers adapter or the JuMP/ToQUBO composition.
Start a Julia session with QUBOPreprocessing and QUBOTools installed as shown on the overview. Run each section's code blocks in order; blocks within a section share their variables.
Preprocess, solve and reconstruct
Consider a binary minimization problem with objective 3bias - x*y. The positive coefficient forces bias=0 in every optimum. Neither x nor y can be fixed by strict dominance at the root (before any assumptions): ties remain until the other variable is known. Here bias is an ordinary binary variable named :bias, not a constant offset.
using QUBOPreprocessing
import QUBOTools as QT
model = QT.Model(Dict(:bias => 3.0, :x => 0.0, :y => 0.0),
Dict((:x, :y) => -1.0))
ws, report = preprocess(model; rules=:dominance)
@assert report.stop_reason == :quiescent
reduced = materialize(ws)
residual = export_model(reduced)
@assert QT.variables(residual) == [:x, :y]
@assert verify_certificate(ws, reduced.certificate.proof).valid
QT.variables(residual)2-element Vector{Symbol}:
:x
:yThere are three different objects here. ws holds reusable working state; reduced captures an owned snapshot of the reduction and its maps; residual is the QUBOTools model to give your solver. Creating and exporting the snapshot are explicit full-model operations, so you choose when to pay for them. The output [:x, :y] shows that bias was removed and that the remaining solver state must list x first and y second. The :quiescent report means propagation has finished for the selected rule; it does not mean the residual is solved. The verify_certificate(...).valid check independently verifies the recorded reduction proof against this workspace. It checks why removing bias is sound; the next step still needs to solve for x and y.
For this two-variable residual, we can solve the whole problem by evaluating its four states. This small enumeration is here to make the example self-contained; use your solver for a larger residual. Its returned vector must contain every free variable in the order shown by QT.variables(residual).
candidates = [[0, 0], [0, 1], [1, 0], [1, 1]]
residual_state = argmin(state -> QT.value(residual, state), candidates)
restored = reconstruct(reduced, residual_state)
original_state = Dict(zip(original_variables(reduced), restored.state))
@assert original_state == Dict(:bias => 0, :x => 1, :y => 1)
@assert restored.energy.finite && restored.energy.value == -1.0
(original_state, restored.energy.value)(Dict(:bias => 0, :y => 1, :x => 1), -1.0)The result assigns bias=0, x=1 and y=1, with original objective value -1. The dictionary makes the original labels explicit; use restored.state directly when your caller already works in original_variables(reduced) order.
reconstruct uses the captured maps to restore bias, validates the complete state, and evaluates the original objective. It does not itself decide whether the residual state is optimal. Here the four-state enumeration supplies that step; with another solver, keep that solver's guarantee. Without caller assumptions, a global residual optimum lifts to an original global optimum.
Select rules=:dominance when you want deductions. Workspace and preprocess default to rules=:identity, which preserves the model without inference and is useful for an off/on comparison.
To run every reduction family, pass rules=:mixed with a time_limit in seconds (see schedule_budgeted!):
- the cheap rules (dominance and low-degree elimination, with pair-relation search capped at a fixed amount of work) always reach their fixpoint, even past the time limit;
- uncapped relation search, roof duality, submodular cuts, Max-Cut, block elimination, residual-SCC contraction and probing share the rest of the budget.
The report shows the time each family took and the variables it removed:
budget_ws, budget_report = preprocess(model; rules=:mixed, time_limit=1.0)
@assert budget_report.stop_reason in (:solved, :fixpoint, :deadline)
[(f.family, f.time_s, f.freed) for f in budget_report.families]1-element Vector{Tuple{Symbol, Float64, Int64}}:
(:cheap, 0.000198483, 3)Sometimes every variable is removed. There is then no free state for a solver to return; reconstruct with an empty vector:
fixed_ws, _ = preprocess(QT.Model(Dict(:z => 2.0),
Dict{Tuple{Symbol,Symbol},Float64}()); rules=:dominance)
fixed_result = materialize(fixed_ws)
fixed_state = reconstruct(fixed_result, Int[])
@assert fixed_state.state == [0]
fixed_state.energy.value0.0Explicit scheduling policies
schedule! centralizes caller policies on a mixed workspace and returns a PolicyScheduleReport with versioned effective settings, family calls/time/removed variables and explicitly skipped families:
ws = Workspace(model; rules=:mixed, integerize_scale=false)
report = schedule!(ws; policy=:legacy_benchmark, allow_weak=false):legacy_benchmark preserves the historical single benchmark sequence and its original-size gates. :legacy_middle lifts relation/block/flow gates while retaining the probing gate. :legacy_census preserves the different census sequence, including conditional cascades and up to eight small-model outer rounds. Their :policy_complete result does not claim an all-family fixpoint. Dimensions are frozen at dispatch; input_edges optionally preserves a source representation's explicit-zero edge count used by an old caller's size gates.
:cheap enables only dominance and low-degree elimination. Its :cheap_quiescent result names that limited guarantee; it skips relations, star-triangle/block elimination, flow/SCC, Max-Cut and probing. This opt-in policy does not establish a new integer-kernel performance result or an expensive-family fixpoint. :budgeted requires time_limit and uses the existing budgeted policy with unchanged defaults. Budgeted double_probe and contract_relations remain false unless explicitly requested for a comparison. All policy times exclude workspace construction, export and independent proof replay.
An optional budgeted on_family(event) callback supports diagnostic call logs and checkpoint-based closure checks. Callback overhead consumes the budget; callback failures propagate after completed deductions, without rolling them back. Observers must not mutate the workspace. Keeping a legacy default is compatible with centralization: mixed short-budget results do not justify a universal noninferiority claim or a default replacement (Refs #95).
Explore assumptions and undo a branch
A branch decision has a different meaning from a deduction. For x - 2x*y, assuming y=0 makes x=0 optimal in that branch. The original problem instead has its minimum at x=y=1. The workspace keeps your assumptions and its conditional deductions separate so undoing the branch also removes the facts that depended on it. Solving this branch alone is therefore insufficient to solve the original problem; the later loop also explores y=1.
using QUBOPreprocessing
import QUBOTools as QT
model = QT.Model(Dict(:x => 1.0, :y => 0.0), Dict((:x, :y) => -2.0))
ws = Workspace(model; rules=:dominance)
@assert propagate!(ws).deductions == 0
root = checkpoint(ws)
update = assume!(ws, :y, 0; max_work=10)
@assert update.stop_reason == :applied
report = propagate!(ws; max_work=100)
@assert report.stop_reason == :quiescent
@assert changes(ws, root) == [:y => 0]
@assert deductions(ws; since=root) == [:x => 0]
(changes(ws, root), deductions(ws; since=root))([:y => 0], [:x => 0])Use original labels with assume!; a label is not a residual index. The two queries above return only fixing records added since the checkpoint, without building a residual. Here changes reports your choice y=0, while deductions reports the consequence x=0. That is enough when a surrounding algorithm only needs to learn which values changed.
To solve or inspect this branch, explicitly capture its residual. Both variables are now fixed, so reconstruction needs no child state. The scope records why this result cannot be treated as a root-global deduction.
branch = materialize(ws)
branch_state = reconstruct(branch, Int[])
@assert branch.certificate.scope == :assumptions
@assert branch_state.energy.value == 0.0
rollback!(ws, root)
@assert isempty(assumptions(ws)) && isempty(deductions(ws))
branch_state.energy.value0.0This branch has energy 0. Rollback returns the workspace to the checkpoint before y=0, removing both that assumption and the deduction x=0, so it can safely explore y=1 next.
The snapshot remains a historical result after rollback; it does not describe the current workspace. Captured proof certificates require the matching current trail and generation when verified against a workspace. See certificate scope and verification before reusing proof evidence.
A search can repeat this pattern. Keep rollback in a finally block so an error in export or solver handling does not leave the next branch conditioned by the previous one. This tiny example covers both values of y; a larger search must supply its own branch coverage, incumbent and termination policy.
branch_energies = Dict{Int,Float64}()
for y_value in (0, 1)
cp = checkpoint(ws)
try
update = assume!(ws, :y, y_value; max_work=10)
@assert update.stop_reason == :applied
report = propagate!(ws; max_work=100)
@assert report.stop_reason == :quiescent
snapshot = materialize(ws)
branch_energies[y_value] = reconstruct(snapshot, Int[]).energy.value
finally
rollback!(ws, cp)
end
end
@assert branch_energies == Dict(0 => 0.0, 1 => -1.0)
@assert isempty(assumptions(ws)) && isempty(deductions(ws))
branch_energiesDict{Int64, Float64} with 2 entries:
0 => 0.0
1 => -1.0The two entries are optima of different restricted problems: y=0 gives energy 0, and y=1 gives -1. Because these branches cover both values of y, the smaller value solves this tiny original problem. In a larger search, comparing some branch results is insufficient without accounting for the remaining branches.
The limits in this example fit its tiny graph. In a real loop, inspect each report: a refused assume! leaves the workspace unchanged, whereas interrupted propagate! retains a sound prefix that you can resume with another call. Each call has its own limits; your search is responsible for its total budget. Branch workloads explains the complete pattern and guarded search example. Bounded dominance describes stop reasons and charged work.
Nested rollback undoes the work since a checkpoint. Removing an older assumption with unfix! instead rebuilds and replays retained assumptions, discarding old deductions and invalidating old checkpoints. Budget that full operation separately; it is not a local update. Use reset! when model coefficients or compiler penalties change. The workspace reference explains both paths.
Let the direct adapter handle the solver boundary
If your solver follows QUBODrivers, sample_preprocessed performs propagation, export, proof verification, child dispatch and reconstruction for you. This is convenient for a complete solve, but it deliberately pays those full boundaries on each call. Prefer the workspace pattern above when an inner loop only needs changed fixings. Consult the measured costs before choosing a default.
Install QUBODrivers with Pkg.add("QUBODrivers"). Loading it activates the optional extension; the core examples above do not need a solver package.
using QUBOPreprocessing
import QUBODrivers as QD
import QUBOTools as QT
model = QT.Model(Dict(:bias => 3.0, :x => 0.0, :y => 0.0),
Dict((:x, :y) => -1.0))
solved = sample_preprocessed(model, QD.ExactSampler.Optimizer;
rules=:dominance, max_child_variables=8)
@show solved.stop_reason solved.optimal solved.scope_optimal
if !isempty(solved.samples)
best = first(solved.samples)
@assert length(best.state) == 3
@assert best.energy.value == -1.0
endPass a factory for a fresh empty child, not a sampler that already holds a model. Model input defaults to dominance in this adapter; an existing workspace retains its chosen rule and caller scope. Samples already contain original-order states and original numerical energies. The example's best state has energy -1. If no sample is returned, inspect solved.stop_reason before changing the solver or retrying with a larger allowance.
Always inspect stop_reason, optimal and scope_optimal as well as the samples. A stop or refusal may return no sample. A heuristic child stays heuristic; a conditional optimum stays conditional. In particular, the supported QUBODrivers 0.6.5 floor reports its generic ExactSampler as locally solved; 0.6.6 corrects its completed public status. The adapter follows that public status, not the solver's name. It also does not preserve a sampling distribution. The consumer reference explains shared work/deadline limits, capacity and result caps, Float64 transport refusals and status handling.
Compose with JuMP and ToQUBO
For a constrained JuMP model, place the qualified factory inside ToQUBO.Optimizer. ToQUBO compiles the source model, preprocessing works on that compiled QUBO, and reconstruction restores every compiled bit before ToQUBO decodes source values. Install JuMP and ToQUBO with Pkg.add(["JuMP", "ToQUBO"]) as well as QUBODrivers.
using QUBOPreprocessing, JuMP
import QUBODrivers as QD
import ToQUBO
source = Model(() -> ToQUBO.Optimizer(() -> QUBOPreprocessing.Optimizer(
QD.ExactSampler.Optimizer; max_child_variables=8)))
@variable(source, x, Bin)
@variable(source, y, Bin)
@objective(source, Min, x - 2y)
@constraint(source, x >= 1)
optimize!(source)
@show termination_status(source) primal_status(source)
@assert has_values(source)
chosen = round.(Int, value.((x, y)))
@assert chosen == (1, 1) && chosen[1] >= 1
@assert objective_value(source) == -1.0The solution is x=1, y=1, which satisfies x ≥ 1 and gives objective -1. has_values checks that there is a result to read; inspect termination_status to decide whether the solver claims an optimum. Check feasibility and objective values in the original source model, as shown here. A certified optimum of an inadequately penalized QUBO can still violate a source constraint. The consumer example and examples/consumer.jl extend this to a bounded integer with several compiled bits.
Choose the next reference
Use models and ownership for accepted input forms, label maps and numerical evaluation, workspaces for update/undo costs, dominance for inference limits, and certificates for independent verification. Full export, verification and reconstruction can scan the source model even when a recent update touched only a small neighborhood. Exact proof arithmetic does not make the reported Float64 energy an exact value.