Iterative Penalty Refinement
The attributes on this page act on the penalty coefficients described in Compiler Settings.
When a solve returns a best sample that violates source constraints — the practical symptom of under-tuned penalties — ToQUBO can re-tune and re-solve automatically inside one optimize! call. Enable the loop with ToQUBO.Attributes.MaxPenaltyUpdates; each iteration checks the best sample with the same measurement as ToQUBO.violations, updates the penalties of violated constraints according to ToQUBO.Attributes.PenaltyUpdateStrategy, recompiles, and samples again, stopping on feasibility, budget exhaustion, or an empty result set.
using JuMP
using QUBODrivers
using ToQUBO
using ToQUBO: Attributes
model = Model(() -> ToQUBO.Optimizer(ExactSampler.Optimizer))
@variable(model, x[1:2], Bin)
@objective(model, Max, 3x[1] + 3x[2])
c = @constraint(model, x[1] + x[2] <= 1)
# Deliberately under-penalize, then let refinement recover feasibility.
set_attribute(c, Attributes.ConstraintEncodingPenaltyHint(), -0.1)
set_attribute(model, Attributes.MaxPenaltyUpdates(), 5)
optimize!(model)
(primal_status(model), objective_value(model))(MathOptInterface.FEASIBLE_POINT, 3.0)The default ToQUBO.Attributes.MultiplicativeUpdate strategy matches MQT QAO's sequential penalty escalation (arXiv:2406.12840): violated constraints' coefficients are multiplied by a factor (default 10) — hinted constraints through their hint (sign preserved), inferred constraints through ToQUBO.Attributes.ConstraintPenaltyScale. The number of iterations performed is queryable afterwards:
get_attribute(model, Attributes.PenaltyUpdateCount())2Each iteration fully recompiles the model; ToQUBO.Attributes.CompilationTime reports the last recompile only, so total refinement overhead scales with the iteration count.
Escalation grows the QUBO's coefficient range, which physical samplers resolve with limited precision. For bounded coefficients, configure constraints with ToQUBO.Attributes.AugmentedLagrangianPenalty and select ToQUBO.Attributes.SubgradientUpdate: the multiplier $\lambda$ is then updated from each iteration's signed residual (method of multipliers), converging with $\rho$ held fixed (Bertsekas 1982; Yonaga–Miyama–Ohzeki, arXiv:2012.06119 run this iteration on a D-Wave annealer), and $\rho$ escalates only after patience consecutive non-improving iterations. Violations driven by variable encodings rather than constraint penalties have no per-constraint coefficient and are not updated by either strategy.
ToQUBO.Attributes.MaxPenaltyUpdates — Type
MaxPenaltyUpdates()Maximum number of penalty-refinement iterations performed inside a single MOI.optimize! call. When greater than zero, after each solve the best sample is checked against the source constraints; while any is violated and the budget is not exhausted, penalties are updated according to PenaltyUpdateStrategy, the model is recompiled, and the sampler is invoked again.
Defaults to 0, which disables refinement and preserves single-solve behavior exactly.
ToQUBO.Attributes.PenaltyUpdateStrategy — Type
PenaltyUpdateStrategy()The PenaltyUpdate strategy applied by the penalty-refinement loop (see MaxPenaltyUpdates). Defaults to MultiplicativeUpdate().
ToQUBO.Attributes.PenaltyUpdate — Type
PenaltyUpdateAbstract type for iterative penalty-update strategies used by the penalty-refinement loop enabled through MaxPenaltyUpdates.
ToQUBO.Attributes.MultiplicativeUpdate — Type
MultiplicativeUpdate(factor::Real = 10.0)Multiplicative penalty escalation (the strategy of MQT QAO, arXiv:2406.12840): after each solve, every source constraint violated by the best sample has its penalty coefficient magnitude multiplied by factor. Hinted constraints have their ConstraintEncodingPenaltyHint multiplied directly (preserving its sign); automatically inferred constraints have their ConstraintPenaltyScale multiplied, which also escalates the constraint's slack-encoding penalty. factor must be finite and greater than one.
Escalation raises the QUBO's coefficient range, which real samplers resolve with limited precision; for a bounded-coefficient alternative see SubgradientUpdate.
ToQUBO.Attributes.SubgradientUpdate — Type
SubgradientUpdate(; step = nothing, patience = 3, escalation_factor = 10.0)Method-of-multipliers penalty refinement for constraints using AugmentedLagrangianPenalty. After each solve, every such constraint's multiplier is updated from the best sample's signed residual $r$: equalities take $\lambda \gets \lambda + \eta r$, inequalities the one-sided $\lambda \gets \max(0, \lambda + \eta r)$ ($r > 0$ when violated). The step $\eta$ defaults to the constraint's own $\rho$, the classical choice. Multiplier updates converge with bounded $\rho$ (Bertsekas 1982), keeping the QUBO's coefficient range stable across iterations — the advantage over MultiplicativeUpdate on samplers with limited coefficient precision.
Safeguard: violated constraints' $\rho$ is escalated by escalation_factor only after patience consecutive iterations without a decrease in the violation norm, then the counter resets. This adapts the classical escalate-only-when-progress-stalls rule (Bertsekas; Conn–Gould– Toint's BCL) to sampled binary problems, whose violation norms are quantized and typically sit unchanged until a constraint flips feasible — a ratio test on consecutive norms would misfire there on every iteration. Constraints not using AugmentedLagrangianPenalty, and constraint sets other than scalar EqualTo/LessThan/GreaterThan, are left untouched by this strategy.
ToQUBO.Attributes.PenaltyUpdateCount — Type
PenaltyUpdateCount()Number of penalty-refinement iterations performed by the last MOI.optimize! call, or nothing before any solve. Zero means the loop was disabled, the first solve was already feasible, or no result was available.