Set Cover

Source: examples/set_cover/README.md

Given a universe of E elements and a collection of S sets, find the minimum sub-collection whose union equals the universe.

QUBO formulation

Input: number of elements E, number of sets S, coverage membership matrix (flat Vec of E*S entries, covers[e][s] = 1 if set s covers element e)
Model: S binary variables. x_s = 1 if set s is selected.
Objective: minimise sum(x_s)
Constraints: per element e: sum_{s: covers[e][s]=1} x_s >= 1 (ATLEAST with k=1)

For each element, the encoder iterates over all sets and uses a branch to conditionally push only covering set indices into the element’s index vector. ATLEAST then enforces that at least one covering set is selected.

DSL methods used

problem.vec() – allocate a vector register for each element’s covering set indices
problem.branch(cond, arm, default) – conditional VECPUSH based on coverage membership
model.apply_atleast(indices, k, penalty) – ATLEAST constraint with k=1

Pipeline overview

CP (xqcp) – generate a random coverage matrix, declare binary variables (one per set), and encode per-element coverage constraints via conditional branching and ATLEAST.
Assemble – .xqasm text to bytecode via xquad.asm
Encode – run encoder on chosen XQVM to produce the XQMX model
Sample – solver runs SA/QPU/GPU over the model
Verify – verifier checks coverage constraints and computes energy
Decode – decoder extracts the selected sets

Usage

uv run python examples/set_cover/runner.py --seed 42
uv run python examples/set_cover/runner.py --num-sets 6 --interpreter rust

Flag	Default	Description
`--num-elements`	`4`	Number of elements in the universe
`--num-sets`	`5`	Number of sets
`--solver`	`dwave-cpu`	Solver backend (see Choosing a solver)
`--interpreter`	`python`	XQVM backend: `python` or `rust`
`--seed`	`42`	Random seed
`-o`	stdout	Write JSON result to file

Choosing a solver

Name	Hardware	Install
`dwave-cpu`	CPU (default)	`pip install xquad`
`dwave-qpu`	D-Wave Leap account	`pip install xquad[dwave]`
`cuda-gpu`	NVIDIA CUDA GPU	`pip install xquad[cuda]`
`metal-gpu`	Apple Silicon (macOS)	`pip install xquad[metal]`

See GPU/QPU installation for driver prerequisites and xqsa solver quick-starts for per-solver parameter tuning.

Non-default solvers will not reproduce the canonical output (different RNG/hardware). example-smoke always runs dwave-cpu.

The canonical output and its invariants are defined in the source README.