XQuad Set Cover 示例深度解析：从集合覆盖问题到 QUBO 编码与端到端流水线
XQuad Set Cover 示例深度解析：从集合覆盖问题到 QUBO 编码与端到端流水线
导读
集合覆盖（Set Cover）是经典的组合优化问题：给定一个由 E 个元素构成的论域和一组 S 个集合，目标是选出数量最少的子集合，使其并集恰好覆盖全部元素。本文以 XQuad 仓库中的 Set Cover 示例 为核心，完整讲解该问题如何用 xqcp 约束编程 DSL 建模为 QUBO、如何在 Python / Rust 两种 XQVM 解释器上端到端运行（编码 → 求解 → 验证 → 解码），并深入剖析 ATLEAST 约束的底层展开原理与各求解器后端的选用方法。读完本文，你将掌握一个可复制的集合覆盖 QUBO 建模范式和一套完整的 XQuad 示例工程运行、调试与验证技能。
问题定义与 QUBO 建模
数学定义
集合覆盖问题的输入为：
- 元素个数 E（universe 的大小）；
- 集合个数 S；
- 覆盖关系矩阵（coverage membership matrix），以
E*S个条目展平传入，covers[e][s] = 1表示集合 s 覆盖元素 e。
模型采用 S 个二元变量，x_s = 1 表示集合 s 被选中，0 表示未选中。由此得到 QUBO 的两个组成部分：
- 目标函数：最小化选中集合的数量，即
min sum(x_s)； - 约束条件：对每个元素 e，要求
sum_{s: covers[e][s]=1} x_s >= 1，即每个元素至少被一个覆盖它的集合选中——这正是ATLEAST约束取 k=1 的形态。
该建模方式的关键技巧在于：每个元素的约束只作用于“覆盖它的那些集合”对应的变量，因此编码器需要按覆盖关系动态构造每个元素的索引向量，而不是把全部 S 个变量塞进同一条约束。
编码器的分支构造法
在 runner.py 的 build_problem 中，约束构造的核心逻辑如下：
# Constraint per element: at least one covering set selected
with problem.range(0, num_elements_in) as e:
elem_indices = problem.vec()
with problem.range(0, num_sets_in) as s:
covers_es = problem.stow("covers_es", covers_in.get(e * num_sets_in + s))
problem.branch(
covers_es,
lambda: elem_indices.push(s),
None,
)
problem.model.apply_atleast(elem_indices, 1, 200)
逐行拆解：
problem.vec()为每个元素分配一个向量寄存器（elem_indices），后续用于存放“覆盖该元素的集合索引”；- 内层
range(0, num_sets_in)遍历全部 S 个集合； covers_in.get(e * num_sets_in + s)从展平的覆盖矩阵输入中读取covers<a href="https://link.gitcode.com/i/293315d50752c2a98851367bb1ba113a" target="_blank">e][s]，problem.stow()将其求值并暂存到寄存器（详见 [problem.py）；problem.branch(cond, arm, default)实现条件分支：当covers_es非零时执行elem_indices.push(s)，把集合 s 的索引压入该元素的向量；否则走默认分支（这里为None，即什么都不做）。branch()的变参语义是 (cond, callable) 成对出现，最后一个参数是必填的默认分支，采用“首条命中即执行”的语义，见 problem.py；- 最终
problem.model.apply_atleast(elem_indices, 1, 200)为该元素施加“至少选中 1 个覆盖集合”的约束，惩罚权重取 200。
DSL 方法的使用与底层含义
示例 README 明确列出的三个 DSL 方法，在源码中都有对应的动作记录与汇编发射逻辑：
| DSL 方法 | 作用 | 底层动作 / 指令 |
|---|---|---|
problem.vec() |
为每个元素的覆盖集合索引分配向量寄存器 | 记录 vec_alloc 动作，返回符号化的 VecRef（见 problem.py） |
problem.branch(cond, arm, default) |
基于覆盖关系条件执行 VECPUSH |
记录 branch 动作，捕获各分支体动作（见 problem.py） |
model.apply_atleast(indices, k, penalty) |
施加 k=1 的至少覆盖约束 | 记录 atleast 动作并发射 ATLEAST 指令（见 symbols.py 与 compiler.py） |
其中 apply_atleast 发射的汇编片段形如：
; 先压入 k，再压入 penalty
PUSH 1
PUSH 0xC8
ATLEAST r<model> r<indices>
在 XQVM 指令集层面，ATLEAST（opcode 0x75）从栈上依次弹出 penalty 和 k，读取 indices 向量寄存器，然后在 model.size 处分配松弛变量并把模型展开为 EQUALITY 形式的惩罚项（见 ISA.md）。DSL 调用 apply_atleast 时传入的 200 即为该惩罚权重。
ATLEAST 约束的底层展开原理
ATLEAST 约束并不是一个独立的惩罚公式，而是通过松弛变量 + EQUALITY 展开实现的，完整推导见 HLF.md：
- 计算
max_excess = N - k（N 为索引向量长度）； - 在
model.size处分配S = floor(log2(max_excess)) + 1个松弛变量，模型大小随之增长； - 构造组合系数向量
[+1, +1, ..., +1, -1, -2, -4, ..., -2^(S-1)]：原变量系数为 +1，松弛变量为负的 2 的幂； - 对组合后的索引与系数执行
EQUALITY展开，目标值取 k。
展开后约束实际表达为：
Σ(x_i) - 1*s_0 - 2*s_1 - ... = k
即：选中数量超过 k 的部分由松弛变量以二进制加权方式吸收，从而把不等式 >= k 精确地改写为等式。需要留意的是：
ATLEAST、ATLEASTW、REDUCE与EQUALITY是 XQVM 中仅有的四个会修改model.size的指令，且新变量一律以追加方式分配在model.size处，既有变量索引不受影响（见 HLF.md）；- 索引超出模型现有大小会抛错，因此编码阶段必须先保证
indices全部合法； ATLEAST的松弛变量分配数量取决于N - k，例如 3 个变量、k=2 时max_excess=1，只需 1 个松弛变量。Set Cover 示例中每个元素的 k=1，松弛变量规模随该元素的覆盖集合数N对数增长，即floor(log2(N-1)) + 1个。
在 xqcp 测试中，同样存在对 ATLEAST 语义的验证：例如 4 个变量、k=2 时，选中 {0,2} 或 {0,1,2} 均合法，而仅选中 {1} 不合法，见 test_xqcp.py。还有测试专门断言 ATLEAST 会增长模型大小，因此与 REDUCE 的“阴影计数器”混用会触发编译期拒绝（见 test_xqcp.py）——这提示我们在建模时不要把“增长模型”的约束与依赖固定模型大小的操作混在同一作用域。
端到端流水线：CP → Assemble → Encode → Sample → Verify → Decode
示例 README 给出了六步流水线，其真实执行流程可在 runner.py 的 run() 函数中逐一对应：
| 步骤 | 参与者 | 关键调用 |
|---|---|---|
1. CP（xqcp） |
生成随机覆盖矩阵、声明二元变量、编码逐元素约束 | build_problem() + problem.compile() |
| 2. Assemble | 把 .xqasm 文本汇编为字节码 |
Rust 后端经 xquad.asm 汇编；Python 后端直接执行源码 |
| 3. Encode | 在选定的 XQVM 上运行 encoder 程序，产出 XQMX 模型 | vm.run(programs.encoder)，输出 slot 0 为模型 |
| 4. Sample | 求解器对模型采样（SA / QPU / GPU） | build_solver(solver_name, seed=seed).solve(model) |
| 5. Verify | 验证样本为二元且每个元素都被覆盖，并计算能量 | vm.run(programs.verifier)，输出 (energy, valid) |
| 6. Decode | 解码出选中的集合列表 | vm.run(programs.decoder)，输出 selected |
problem.compile() 会一次性生成三份 .xqasm 程序字符串（encoder、verifier、decoder），并立即用字节码验证器（Phase 1 + Phase 2）对三份程序做编译期校验，校验失败会抛出 ValueError；只有当 xqffi 扩展不可用时该校验会被静默跳过（见 problem.py）。
run() 中的三个 VM 实例分别执行 encoder / verifier / decoder，calldata 的接续关系为：
- encoder 输入
[num_elements, num_sets, flat_covers]，输出 1 个 slot 的XQMX模型； - verifier 输入
[num_elements, num_sets, flat_covers, model, sample]，输出(energy, valid)两个 slot； - decoder 输入
[sample, num_sets]，输出 1 个 slot 的Vec，再逐位取出得到selected列表。
VM 统一封装了 Rust FFI 与纯 Python 参考实现两种后端，set_calldata() 与 set_output_slots() 负责装配输入输出，且 calldata 中的 XQMX 会同时在校验点与运行期被检查（见 vm.py）。
main() 的最后还会计算 num_selected 与 is_valid：is_valid_cover() 逐元素验证“至少有一个被选集合覆盖它”，并把全部结果序列化为 JSON（sort_keys=True、缩进 2），输出到 stdout 或 -o 指定的文件（见 runner.py）。
命令行用法与参数详解
从仓库根目录直接运行：
uv run python examples/set_cover/runner.py --seed 42
uv run python examples/set_cover/runner.py --num-sets 6 --interpreter rust
全部命令行参数及其默认值如下（与 runner.py 的 argparse 定义一致）：
| Flag | 默认值 | 说明 |
|---|---|---|
--num-elements |
4 |
论域中的元素个数 E |
--num-sets |
5 |
集合个数 S |
--solver |
dwave-cpu |
求解器后端（见下方“选择求解器”） |
--interpreter |
python |
XQVM 后端：python 或 rust |
--seed |
42 |
随机种子 |
-o |
stdout | 将 JSON 结果写入指定文件 |
关于参数的两个重要辨析：
--interpreter与--solver是两个独立维度：前者选择执行 encoder/verifier/decoder 三份程序的 VM（xqvm_py纯 Python 参考实现或经xqffi调用的 Rust 解释器），后者选择采样 XQMX 模型的求解器。一个正确的模型在两个解释器上必然产生相同的valid与energy（详见 using-examples.md）；- 解码结果可能因解释器而异：当模型存在多个能量相等的等价最优解时，求解器只会返回其中某一个。
set_cover在默认种子下恰好存在这种“平局”，因此--interpreter rust与默认的python可能解码出不同的selected，但两者同样合法。这一点在 using-examples.md 中被明确点出。
随机覆盖矩阵的生成
main() 中覆盖矩阵的生成逻辑是（见 runner.py）：
rng = random.Random(args.seed)
covers = [[0] * args.num_sets for _ in range(args.num_elements)]
for e in range(args.num_elements):
covers[e][rng.randrange(args.num_sets)] = 1 # 保证每个元素至少被一个集合覆盖
for e in range(args.num_elements):
for s in range(args.num_sets):
if rng.random() < 0.4:
covers[e][s] = 1 # 以 40% 概率随机补充覆盖
第一轮循环保证问题一定有可行解（每个元素至少有一个覆盖集合），第二轮以 0.4 概率随机增补覆盖关系，使矩阵更接近真实场景。
选择求解器：SA / QPU / GPU / Quip
示例 README 给出了五种求解器后端，它们对应 xqsa/registry.py 中的 SOLVERS 注册表：
| 名称 | 硬件 | 安装方式 |
|---|---|---|
dwave-cpu |
CPU（默认） | pip install xquad |
dwave-qpu |
D-Wave Leap 账户 | pip install xquad[dwave] |
cuda-gpu |
NVIDIA CUDA GPU | pip install xquad[cuda] |
metal-gpu |
Apple Silicon（macOS） | pip install xquad[metal] |
quip |
Quip Network（远程矿工，环境变量配置） | pip install xqsa[quip] |
要点：
- 默认求解器
dwave-cpu是无额外依赖的 CPU 模拟退火（SA）实现，DEFAULT_SOLVER = "dwave-cpu"定义于 registry.py，并有测试保证该默认值始终是注册表中的合法键（见 test_registry.py）； - 只有经典 SA 族（
dwave-cpu、cuda-gpu、metal-gpu）的构造器接受seed以保证可复现；D-Wave QPU 是物理硬件没有种子概念，quip由环境配置驱动，两者都会忽略传入的 seed（见 registry.py 与build_solver的实现）； - 非默认求解器由于 RNG / 硬件差异，不会复现 canonical 输出——这正是示例 README 强调的“Non-default solvers will not reproduce the canonical output”；
- GPU/QPU 的驱动前置条件可参见 README.md（如 CUDA 12.x 驱动、D-Wave Leap API token、
QUIP_RPC_URL与配置好的签名器），更多逐求解器参数调优速查见 xqsa/README.md； - extras 可以组合安装，例如
pip install xquad[cuda,dwave]。
Canonical 输出与冒烟测试
示例 README 明确说明了 canonical 输出约定：example-smoke 冒烟测试会同时用两种解释器在 --seed 42 --solver dwave-cpu 下运行，只校验 valid == 1，不要求两个解释器输出逐字节一致。这一“基于不变量的验证”策略在 example-smoke.py 的模块文档字符串中写得很清楚：SA 对 BQM 的构造顺序敏感，两种路径可能找到不同但同样合法的能量最优解。
冒烟测试的执行逻辑（见 example-smoke.py）：
- 遍历全部 14 个示例目录，对每个 runner 分别用
python与rust两种解释器运行，检查valid == 1； - 对清单中标有
hardware: true的子集（maxcut、tsp、knapsack，见 manifest.yaml），在硬件求解器可用时额外以rust解释器跑一轮硬件求解。set_cover不在硬件子集中，但无论该标志如何，每个示例在两种解释器上都会跑 CPU 退火器； - 任何
valid != 1都会计入失败并返回非零退出码。
因此，若你修改了示例或自建问题，请记住：valid == 1 是流水线正确性的判据，而 selected 的具体内容是求解器在（可能存在多个的）能量最优解中挑选的结果，二者不可混为一谈。
小结
通过 examples/set_cover，我们完整看到了 XQuad 处理一个 NP 难组合优化问题的标准范式：以 xqcp DSL 声明输入、模型、目标与约束，用 problem.branch() 按数据条件构造约束变量集合，用 apply_atleast(indices, k, penalty) 以“松弛变量 + EQUALITY 展开”的方式把覆盖约束精确写入 QUBO，再经 problem.compile() 生成 encoder / verifier / decoder 三份程序，最后在 VM（Python 或 Rust）与求解器（SA / QPU / GPU / Quip）之上完成 编码 → 求解 → 验证 → 解码 的端到端闭环。这套模式同样适用于加权集合覆盖、顶点覆盖、背包等“选择子集满足覆盖/容量约束”的问题家族，是理解 XQuad 建模与求解流水线的最佳入门范本之一。