Executable examples
The code below is read from the repository scripts during the build, so there is one executable source for each example. All children are public ExactSampler instances and need no credentials. After dependency setup the scripts work offline. The ExactSampler version contract distinguishes the 0.6.5 public-status defect from corrected 0.6.6 completion. Heuristic neighborhood solves do not certify a coupled global optimum, even when a fixture reaches its known optimum.
For standalone ToQUBO setup and execution, see the example environment instructions. The docs environment can also run all six scripts directly.
Fitting whole model
# SPDX-License-Identifier: MPL-2.0
using QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
optimizer = QUBODecomposition.Optimizer(
child_optimizer = () -> QUBODrivers.ExactSampler.Optimizer(),
max_variables = 3,
strategy = :whole_model,
seed = 123,
)
source = MOI.Utilities.Model{Float64}()
x = MOI.add_variables(source, 3) # x[3] is an isolate
for v in x
MOI.add_constraint(source, v, MOI.ZeroOne())
end
f = MOI.ScalarQuadraticFunction(
[MOI.ScalarQuadraticTerm(4.0, x[1], x[2])],
[MOI.ScalarAffineTerm(-3.0, x[1]), MOI.ScalarAffineTerm(2.0, x[2])],
5.0,
)
MOI.set(source, MOI.ObjectiveFunction{typeof(f)}(), f)
MOI.set(source, MOI.ObjectiveSense(), MOI.MIN_SENSE)
map = MOI.copy_to(optimizer, source)
MOI.optimize!(optimizer)
@assert MOI.get(optimizer, MOI.ObjectiveValue()) == 2.0
@assert MOI.get(optimizer, MOI.VariablePrimal(), map[x[1]]) == 1.0
@assert MOI.get(optimizer, MOI.VariablePrimal(), map[x[2]]) == 0.0
expected_status = pkgversion(QUBODrivers) >= v"0.6.6" ? MOI.OPTIMAL : MOI.LOCALLY_SOLVED
@assert MOI.get(optimizer, MOI.TerminationStatus()) == expected_status
@assert length(QUBOTools.state(optimizer, 1)) == 3
(; objective=MOI.get(optimizer, MOI.ObjectiveValue()), status=MOI.get(optimizer, MOI.TerminationStatus()))(objective = 2.0, status = MathOptInterface.OPTIMAL)Larger than child capacity
# SPDX-License-Identifier: MPL-2.0
using QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
# Four coupled logical variables, one isolate, and a fixed sixth variable.
# Each child handles at most two free variables. Even certified ExactSampler
# neighborhood optima cannot establish a coupled global proof.
optimizer = QUBODecomposition.Optimizer(
child_optimizer = () -> QUBODrivers.ExactSampler.Optimizer(),
max_variables = 2,
strategy = :components_then_sweeps,
max_sweeps = 10,
stagnation_sweeps = 2,
seed = 123,
)
source = MOI.Utilities.UniversalFallback(MOI.Utilities.Model{Float64}())
x = MOI.add_variables(source, 6)
for v in x
MOI.add_constraint(source, v, MOI.ZeroOne())
end
MOI.add_constraint(source, x[6], MOI.EqualTo(1.0))
f = MOI.ScalarQuadraticFunction(
[MOI.ScalarQuadraticTerm(4.0, x[1], x[2]),
MOI.ScalarQuadraticTerm(-2.0, x[2], x[3]),
MOI.ScalarQuadraticTerm(1.0, x[3], x[4])],
[MOI.ScalarAffineTerm(-3.0, x[1]), MOI.ScalarAffineTerm(2.0, x[2]),
MOI.ScalarAffineTerm(-1.0, x[3]), MOI.ScalarAffineTerm(-2.0, x[5]),
MOI.ScalarAffineTerm(3.0, x[6])],
5.0,
)
MOI.set(source, MOI.ObjectiveFunction{typeof(f)}(), f)
MOI.set(source, MOI.ObjectiveSense(), MOI.MIN_SENSE)
map = MOI.copy_to(optimizer, source)
MOI.optimize!(optimizer)
full_state = [MOI.get(optimizer, MOI.VariablePrimal(), map[v]) for v in x]
energy = 5 - 3*full_state[1] + 2*full_state[2] - full_state[3] -
2*full_state[5] + 3*full_state[6] + 4*full_state[1]*full_state[2] -
2*full_state[2]*full_state[3] + full_state[3]*full_state[4]
@assert length(full_state) == 6 && full_state[6] == 1
@assert energy == MOI.get(optimizer, MOI.ObjectiveValue())
@assert MOI.get(optimizer, MOI.TerminationStatus()) == MOI.LOCALLY_SOLVED
@assert all(length(c["selected_indices"]) <= 2 for c in QUBOTools.metadata(QUBOTools.solution(optimizer))["decomposition"]["calls"])
println((; full_state, energy, status=MOI.get(optimizer, MOI.TerminationStatus())))
(; full_state, energy, status=MOI.get(optimizer, MOI.TerminationStatus()))(full_state = [1.0, 0.0, 1.0, 0.0, 1.0, 1.0], energy = 2.0, status = MathOptInterface.LOCALLY_SOLVED)Certified root capacity reduction (0.1.5 or later)
Strict root evidence removes a connector and exposes two child-fitting components. The comparison uses the same two-variable child capacity and explicit total work allowance. The disabled path's capacity refusal is retained; this example makes no timing claim. See root preprocessing for scope, budgets and lifting guarantees.
# SPDX-License-Identifier: MPL-2.0
module RootPreprocessingExample
import QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
function run()
labels=[11,7,30,9,4]
model=QUBOTools.Model{Int,Float64,Int}(labels,[2],[6.0],
[2,2,2,2,1,4],[1,3,4,5,3,5],fill(-1.0,6))
scalar(x)=6*x[2]-x[2]*(x[1]+x[3]+x[4]+x[5])-x[1]*x[3]-x[4]*x[5]
n=QUBOTools.dimension(model)
n<=8 || error("tiny reference guard precedes exponentiation")
optimum=minimum(scalar([isodd(mask>>(i-1)) ? 1 : 0 for i in 1:n]) for mask in 0:(1<<n)-1)
outcomes=Dict{Symbol,Any}()
for mode in (:off,:dominance)
opt=QUBODecomposition.Optimizer(child_optimizer=QUBODrivers.ExactSampler.Optimizer,
max_variables=2,strategy=:components,preprocessing=mode,max_work=100_000)
QUBODrivers.set_model!(opt,model);MOI.optimize!(opt)
data=QUBOTools.metadata(QUBOTools.solution(opt))["decomposition"]
outcomes[mode]=(;opt,data,status=MOI.get(opt,MOI.TerminationStatus()))
end
on,off=outcomes[:dominance],outcomes[:off]
@assert off.status===MOI.INVALID_OPTION # one connected five-variable component
@assert on.status in (MOI.OPTIMAL,MOI.LOCALLY_SOLVED) # actual installed child status
@assert on.data["preprocessing"]["residual_dimension"]==4
@assert on.data["components"]==[[1,3],[4,5]]
@assert on.data["attempted_calls"]==2
@assert all(length(c["selected_indices"])<=2 for c in on.data["calls"])
state=QUBOTools.state(on.opt,1)
@assert length(state)==5 && scalar(state)==QUBOTools.value(on.opt,1)==optimum==-2
return (;status=on.status,original_variables=n,residual_variables=4,child_calls=2,
original_energy=optimum,work_reserved=on.data["work"]["used"],off_status=off.status)
end
end
if abspath(PROGRAM_FILE)==@__FILE__
println(RootPreprocessingExample.run())
end
RootPreprocessingExample.run()(status = MathOptInterface.OPTIMAL, original_variables = 5, residual_variables = 4, child_calls = 2, original_energy = -2, work_reserved = 1904, off_status = MathOptInterface.INVALID_OPTION)ToQUBO refinement
The weak penalty gives decoded source objective 11, compiled objective 10.9 and INFEASIBLE_POINT. Refinement checks actual source residuals and reaches source objective 8 for this fixture. Budget two uses sweeps; budget eight fits all three bits.
# SPDX-License-Identifier: MPL-2.0
module RefinementExample
using JuMP, ToQUBO, QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
function run(; budget=2)
composite=QUBODecomposition.Optimizer(
child_optimizer=()->QUBODrivers.ExactSampler.Optimizer(),
max_variables=budget,seed=123,max_child_calls=100,
# Include the initial evaluation and every row of every child scan.
max_candidate_evaluations=1+100*2^budget,
)
model=Model(()->ToQUBO.Optimizer(()->composite))
@variable(model,x[1:2],Bin)
@objective(model,Max,5+3*x[1]+3*x[2])
c=@constraint(model,x[1]+x[2]<=1)
set_attribute(c,ToQUBO.Attributes.ConstraintEncodingPenaltyHint(),-0.1)
optimize!(model)
@assert primal_status(model)==MOI.INFEASIBLE_POINT
@assert ToQUBO.source_objective_value(model)==11
@assert objective_value(model)≈10.9 # source objective minus the weak penalty
set_attribute(model,ToQUBO.Attributes.MaxPenaltyUpdates(),5)
optimize!(model)
state=value.(x)
@assert state[1]+state[2]<=1
@assert isempty(ToQUBO.violations(model))
@assert ToQUBO.source_objective_value(model)==5+3*sum(state)
expected_status = budget >= 3 && pkgversion(QUBODrivers) >= v"0.6.6" ? MOI.OPTIMAL : MOI.LOCALLY_SOLVED
@assert termination_status(model)==expected_status
@assert length(QUBOTools.state(composite,1))==3
# With B=2, three compiled bits exceed child capacity. Even exact child
# neighborhoods have no coupled global certificate. Fitting exhaustive solves
# expose OPTIMAL with QUBODrivers >=0.6.6, after its public-status correction.
return (; state,source_objective=ToQUBO.source_objective_value(model),
penalized_objective=objective_value(model),status=termination_status(model),
source_feasible=ToQUBO.is_feasible(model),
updates=get_attribute(model,ToQUBO.Attributes.PenaltyUpdateCount()))
end
end
if abspath(PROGRAM_FILE)==@__FILE__
println(RefinementExample.run(;budget=2))
println(RefinementExample.run(;budget=8))
end
small = RefinementExample.run(; budget=2)
fitting = RefinementExample.run(; budget=8)
@assert small.source_feasible && fitting.source_feasible
@assert small.source_objective == fitting.source_objective == 8
(; small, fitting)(small = (state = [0.0, 1.0], source_objective = 8.0, penalized_objective = 8.0, status = MathOptInterface.LOCALLY_SOLVED, source_feasible = true, updates = 2), fitting = (state = [0.0, 1.0], source_objective = 8.0, penalized_objective = 8.0, status = MathOptInterface.OPTIMAL, source_feasible = true, updates = 2))Caller-owned deadline
The outer loop charges compilation, copying, execution and source checks against one absolute allowance. Cancellation remains cooperative for opaque children.
# SPDX-License-Identifier: MPL-2.0
module DeadlineExample
using JuMP, ToQUBO, QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
# The caller owns an absolute deadline. Compile without an internal optimizer,
# then dispatch the compiled model with only the remaining time. Source analysis
# is explicit for this small fixture; project every bit before evaluating it.
function run(; seconds=60.0,max_updates=5,budget=2,
child=()->QUBODrivers.ExactSampler.Optimizer(),
clock=()->time_ns()/1e9,checkpoint=_ -> nothing)
deadline=clock()+seconds
compiler=ToQUBO.Optimizer()
model=Model(()->compiler)
@variable(model,x[1:2],Bin)
@objective(model,Max,5+3*x[1]+3*x[2])
c=@constraint(model,x[1]+x[2]<=1)
set_attribute(model,ToQUBO.Attributes.MaxPenaltyUpdates(),0)
composite=QUBODecomposition.Optimizer(;child_optimizer=child,max_variables=budget,
max_child_calls=100,max_candidate_evaluations=1+100*2^budget)
composite.clock=clock
dispatched_limits=Float64[]
history=Any[]
reason=:updates
for k in 0:max_updates
clock()>=deadline && (reason=:deadline;break)
set_attribute(c,ToQUBO.Attributes.ConstraintEncodingPenaltyHint(),-0.1*10.0^k)
optimize!(model) # compilation time is charged before dispatch
checkpoint(:compiled)
clock()>=deadline && (reason=:deadline;break)
target=MOI.get(compiler,ToQUBO.Attributes.TargetModel())
map=MOI.copy_to(composite,target)
checkpoint(:copied)
remaining=deadline-clock()
remaining<=0 && (reason=:deadline;break)
MOI.set(composite,MOI.TimeLimitSec(),remaining)
push!(dispatched_limits,remaining)
MOI.optimize!(composite)
checkpoint(:solved)
MOI.get(composite,MOI.ResultCount())==0 && (reason=:empty;break)
bits=Dict(v=>MOI.get(composite,MOI.VariablePrimal(),map[v])
for v in MOI.get(target,MOI.ListOfVariableIndices()))
decoded=ToQUBO.project_original_state(compiler,bits)
a,b=decoded[index(x[1])],decoded[index(x[2])]
residual=a+b-1
source_value=5+3*a+3*b
push!(history,(;bits=copy(bits),decoded=[a,b],residual,source_value,
penalized_value=MOI.get(composite,MOI.ObjectiveValue()),
status=MOI.get(composite,MOI.TerminationStatus())))
checkpoint(:checked) # feasibility work is charged before the next round
clock()>=deadline && (reason=:deadline;break)
if residual<=1e-6
reason=:feasible;break
end
end
# A synchronous opaque child may overrun. Checks prevent subsequent dispatch;
# they cannot preempt that child. CompilationTime is only the last compile.
return (;reason,history,dispatched_limits,deadline,
last_compilation_sec=MOI.get(compiler,ToQUBO.Attributes.CompilationTime()),
composite_effective_sec=QUBODrivers.effective_time(composite))
end
end
if abspath(PROGRAM_FILE)==@__FILE__
println(DeadlineExample.run())
end
result = DeadlineExample.run()
@assert result.reason == :feasible
@assert last(result.history).source_value == 8
(; reason=result.reason, final=last(result.history))(reason = :feasible, final = (bits = Dict{MathOptInterface.VariableIndex, Float64}(MOI.VariableIndex(2) => 1.0, MOI.VariableIndex(3) => 0.0, MOI.VariableIndex(1) => 0.0), decoded = [0.0, 1.0], residual = 0.0, source_value = 8.0, penalized_value = 8.0, status = MathOptInterface.LOCALLY_SOLVED))Separator conditioning
With QUBODrivers 0.6.5, this example reaches its call cap after complete uncertified work and reports ITERATION_LIMIT. With the corrected 0.6.6 public certificate, the last call completes proof and returns OPTIMAL even at the exact allowance. Both paths retain the optimum found; an incomplete scan cannot certify it.
# SPDX-License-Identifier: MPL-2.0
module SeparatorExample
using QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
function run(; separator=[1])
# The separator value 1 initially costs +2, but completed leaves give -4.
model = QUBOTools.Model{Symbol,Float64,Int}([:center,:left,:right],
[1,2,3],[2.,1.,1.],[1,1],[2,3],[-4.,-4.])
optimizer = QUBODecomposition.Optimizer(
child_optimizer=()->QUBODrivers.ExactSampler.Optimizer(),
max_variables=1, strategy=:separator, separator=separator, max_separator_size=1,
max_child_calls=4, max_candidate_evaluations=32, seed=41)
QUBODrivers.set_model!(optimizer,model)
MOI.optimize!(optimizer)
@assert QUBOTools.state(optimizer,1)==[1,1,1]
@assert QUBOTools.value(optimizer,1)==-4.
certified = pkgversion(QUBODrivers) >= v"0.6.6"
# The last call completes proof before the cap when the child is certified.
@assert MOI.get(optimizer,MOI.TerminationStatus())===(certified ? MOI.OPTIMAL : MOI.ITERATION_LIMIT)
proof=QUBOTools.metadata(QUBOTools.solution(optimizer))["decomposition"]["separator"]
@assert proof["completed_branches"]==2 && proof["proof_complete"]==certified
@assert proof["incomplete_reason"]==(certified ? nothing : "uncertified_components")
return (;state=QUBOTools.state(optimizer,1), energy=QUBOTools.value(optimizer,1),
status=MOI.get(optimizer,MOI.TerminationStatus()), proof)
end
function compare()
automatic = run(;separator=:articulation)
manual = run(;separator=automatic.proof["indices"])
@assert automatic.state == manual.state && automatic.energy == manual.energy
@assert automatic.status == manual.status
@assert automatic.proof["indices"] == [1]
return (;automatic,manual,discovery_sec=automatic.proof["discovery"]["elapsed_sec"])
end
function refusal()
# Removing any cycle vertex leaves a fitting path, but it is not articulation.
model = QUBOTools.Model{Int,Float64,Int}(collect(1:4),collect(1:4),ones(4),
[1,2,3,1],[2,3,4,4],fill(-2.,4))
results = map((:articulation,[1])) do separator
optimizer = QUBODecomposition.Optimizer(
child_optimizer=()->QUBODrivers.ExactSampler.Optimizer(),
max_variables=3,strategy=:separator,separator=separator,
max_child_calls=4,max_candidate_evaluations=64)
QUBODrivers.set_model!(optimizer,model); MOI.optimize!(optimizer)
return optimizer
end
automatic,manual = results
@assert MOI.get(automatic,MOI.TerminationStatus()) === MOI.INVALID_OPTION
data=QUBOTools.metadata(QUBOTools.solution(automatic))["decomposition"]
@assert data["attempted_calls"] == 0
@assert data["separator"]["discovery"]["reason"] == "no_supported_articulation"
expected_status = pkgversion(QUBODrivers) >= v"0.6.6" ? MOI.OPTIMAL : MOI.LOCALLY_SOLVED
@assert MOI.get(manual,MOI.TerminationStatus()) === expected_status
return (;automatic_status=MOI.get(automatic,MOI.TerminationStatus()),
manual_status=MOI.get(manual,MOI.TerminationStatus()),diagnostic=data["diagnostic"])
end
end
SeparatorExample.compare()
SeparatorExample.refusal()
result = SeparatorExample.compare()
(; result.automatic.state, result.automatic.energy, result.automatic.status,
separator=result.automatic.proof["indices"], result.discovery_sec)(state = [1, 1, 1], energy = -4.0, status = MathOptInterface.OPTIMAL, separator = [1], discovery_sec = 1.2332e-5)Automatic and supplied selection use the identical selected separator, child, start and budgets. Discovery timing is a subset of preparation. A cycle refuses automatic selection even though a supplied separator is supported:
SeparatorExample.refusal()(automatic_status = MathOptInterface.INVALID_OPTION, manual_status = MathOptInterface.OPTIMAL, diagnostic = "no supported articulation separator leaves every residual component within max_variables 3; this does not establish infeasibility or absence of other separators")The bounded comparison compares direct enumeration, all existing sweep selectors and automatic/supplied separator branches using the same guarded child and independent scalar oracles.
Graph-partition regions
# SPDX-License-Identifier: MPL-2.0
import MathOptInterface as MOI
import QUBODrivers, QUBOTools, QUBODecomposition
include(joinpath(@__DIR__, "region_growing.jl"))
edges = [(1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(5,6)]
model = QUBOTools.Model{Int,Float64,Int}(collect(1:7),collect(1:7),
[1.,1.,1.,1.,1.,1.,-0.5],first.(edges),last.(edges),[-2.,-2.,-2.,4.,-2.,-2.,-2.];offset=7.25)
# Capacity three bounds every exhaustive child to eight binary assignments.
optimizer = QUBODecomposition.Optimizer(child_optimizer=QUBODrivers.ExactSampler.Optimizer,
max_variables=3,selection=:partition,partition_plan=PartitionExample.region_growing,
max_child_calls=16,max_candidate_evaluations=129,max_sweeps=3,stagnation_sweeps=1,seed=41)
QUBODrivers.set_model!(optimizer,model)
MOI.optimize!(optimizer)
full_state = QUBOTools.state(optimizer,1)
energy = QUBOTools.value(optimizer,1)
partition = QUBOTools.metadata(QUBOTools.solution(optimizer))["decomposition"]["partition"]
@assert sort(vcat(partition["blocks"]...)) == collect(1:7)
@assert all(length(b) <= 3 for b in partition["blocks"])
@assert energy == QUBOTools.value(model,full_state)
@assert MOI.get(optimizer,MOI.TerminationStatus()) !== MOI.OPTIMAL
(; full_state, energy, partition, status=MOI.get(optimizer, MOI.TerminationStatus()))(full_state = [1, 1, 1, 0, 0, 0, 1], energy = 3.75, partition = Dict{String, Any}("block_sizes" => [3, 3, 1], "cut_absolute_weight" => 4.0, "blocks" => [[1, 2, 3], [4, 5, 6], [7]], "cut_edges" => 1, "planning_sec" => 0.382485288), status = MathOptInterface.LOCALLY_SOLVED)Certified separator pruning
The offline pruning example uses separator_pruning=true, saves child dispatches, and keeps truthful public child statuses. The paired comparison records complete wall time and bound preparation as well as dispatch counts.
result = SeparatorPruningExample.run()
(calls=result.data["attempted_calls"],
pruned=result.data["separator"]["certified_pruned_branches"],
proof_complete=result.data["separator"]["proof_complete"])(calls = 2, pruned = 1, proof_complete = true)The consensus example uses bounded exact children and exposes a persistent duality gap; see the consensus contract.
The coarse offline example coordinates two whole-group flips using two macrovariables for four originals. The coarse manual records its conservative heuristic guarantee.
(; state=x, energy=QUBOTools.value(optimizer,1), status=MOI.get(optimizer,MOI.TerminationStatus()))(state = [1, 1, 1, 1], energy = -4.0, status = MathOptInterface.LOCALLY_SOLVED)Sample-guided fixing with a biased pool
# SPDX-License-Identifier: MPL-2.0
module SampleFixingExample
using QUBODecomposition, QUBODrivers, QUBOTools
import MathOptInterface as MOI
include("guarded_child.jl")
function run()
labels=[:a,:b,:c,:isolate]
model=QUBOTools.Model{Symbol,Float64,Int}(labels,[1,2,3],[4.,-2.,-1.],
Int[],Int[],Float64[];start=Dict(zip(labels,[0,1,1,0])))
pool=(;labels,domain=:bool,assignments=[[1,0,0,0],[1,1,0,0],[1,0,1,0]],
provenance="explicit biased demonstration pool; not generated samples")
work=Ref(0); dimensions=Int[]
optimizer=QUBODecomposition.Optimizer(strategy=:sample_fixing,sample_pool=pool,
max_variables=2,max_child_calls=4,max_candidate_evaluations=32,child_optimizer=()->SampleFixingExactChild(work,dimensions))
MOI.set(optimizer,MOI.TimeLimitSec(),10.)
QUBODrivers.set_model!(optimizer,model)
MOI.optimize!(optimizer)
data=QUBOTools.metadata(QUBOTools.solution(optimizer))["decomposition"]
info=data["sample_fixing"]
x=QUBOTools.state(optimizer,1)
@assert x == [0,1,1,0] && QUBOTools.value(optimizer,1) == 4x[1]-2x[2]-x[3] == -3.
@assert info["fixed_variables"] == Dict(1=>1,4=>0)
@assert !info["global_incumbent_compatible"] && !info["original_proof"]
@assert info["reported_generation_sec"] === nothing
@assert dimensions == [2] && work[] == 4
@assert MOI.get(optimizer,MOI.TerminationStatus()) === MOI.LOCALLY_SOLVED
return (;optimizer,state=copy(x),energy=QUBOTools.value(optimizer,1),
status=MOI.get(optimizer,MOI.TerminationStatus()),metadata=QUBOTools.metadata(QUBOTools.solution(optimizer)),
child_assignments=work[],child_dimensions=copy(dimensions))
end
end
if abspath(PROGRAM_FILE) == @__FILE__
result=SampleFixingExample.run()
println((;state=result.state,energy=result.energy,status=result.status,child_assignments=result.child_assignments))
end
result=SampleFixingExample.run()
(; incumbent=result.state, status=result.status)(incumbent = [0, 1, 1, 0], status = MathOptInterface.LOCALLY_SOLVED)