在QUBO中对变量进行探测可提升借助roof dual达到全局最小的概率

《Frontiers in Computer Science》：Probing variables in QUBOs improves the probability of reaching the global minimum with the roof dual

　　

二次无约束二值优化（QUBO）问题因量子退火技术的发展而备受关注，该技术致力于求解此类问题。求解QUBO问题即寻找其目标函数的全局最小值。文献中已提出多种经典预处理与求解方法，本研究聚焦于roof dual——一种对QUBO全局最小值的确定性下界。重要的是，在某些情况下，roof dual计算除提供有效下界外，还能揭示达到全局最小的解。研究人员开发了一种基于探测（即对特定变量进行穷举枚举）的QUBO求解算法。具体而言，研究人员证明对变量集合进行探测可提高借助roof dual达到全局最小的概率，并证明了一个理论结果，用以检验探测过程中是否找到了全局最小。尽管所提算法运行时间为指数级，实证研究表明，相较于暴力枚举及若干其他前沿算法，该算法能更快求得随机QUBO与最大团（MC）问题QUBO的全局最小。

研究背景与动机

二次无约束二值优化（Quadratic Unconstrained Binary Optimization，QUBO）作为0-1整数规划的特例，在一般情形下为NP-hard问题，且大量具有实际意义的NP-hard问题均可表述为QUBO形式。随着量子退火技术聚焦于求解QUBO，发展通用且精确的QUBO求解算法成为迫切需求。已有研究如Tarjan、Karp等针对最大团（Maximum Clique，MC）、图着色、最小顶点覆盖等问题提出专用精确算法，但无法通用于任意QUBO形式。roof dual由Hammer等人与Boros和Hammer提出，可在多项式时间内给出QUBO全局最小的确定性下界，并在某些情况下通过2-SAT计算揭示全局解；Boros等人与Rother等人指出，将变量探测（probing，即对部分变量穷举枚举）与roof dual结合可提升效率，但既有方法不保证完全求解或给出全局最小保证。因此，研究人员开展本研究，旨在构建一种基于探测与roof dual的通用精确QUBO求解算法，并证明探测中判定全局最小的理论条件。该研究发表于《Frontiers in Computer Science》。

主要关键技术方法

研究人员采用的核心方法包括：将QUBO改写为仅含正系数的posiform（二次正系数形式）；通过构造容量网络G_P并运行最大流计算（如Edmonds-Karp算法）提取交替和（alternating sum）以提升常数偏移C得到roof dual下界C₂；将残余posiform的线性与二次项转化为2-SAT问题以判定roof dual是否为全局最小（即可解性solvability）；在探测阶段对选定变量子集进行穷举赋值，每次固定后重算roof dual与2-SAT，利用所证定理（若最低roof dual界对应可解2-SAT则必为全局最小）提前终止。实验部分使用随机生成QUBO与最大团（MC）问题QUBO两类样本，对比暴力枚举、分支定界、迭代roof dual（Boros等，2008）、QPBO（Rother等，2007）、SDPA半定规划等算法。

研究结果

2 Review of previous research

研究人员系统回顾了roof dual的计算框架：QUBO经代数操作转为posiform，其中负系数线性项与二次项通过引入补变量x?_i=1-x_i化为正系数；所有交替和对应容量网络中的增广路，最大流值ν使常数偏移提升至C+ν，得roof dual C₂；残余posiform P₂的线性项z与二次项zz′分别生成2-SAT子句?z∨?z与?z∨?z′，若2-SAT可解则C₂即为全局最小。该节为后续算法奠定理论基础。

3 理论结果与算法（原文Section 3）

研究人员证明新定理：若在探测过程中，对某一变量赋值后所得子问题的最低roof dual界C₂对应的残余posiform P₂经2-SAT判定可解，则该2-SAT解还原回原变量即全局最小。基于此，提出探测算法：逐层选取变量集进行穷举，每固定一组赋值即算roof dual与2-SAT，一旦可解即返回全局最小并终止；若所有探测分支穷尽仍未可解，则退化为暴力枚举但实测分支数远小于2ⁿ。算法虽最坏指数时间，但借助roof dual剪枝显著提升命中率。

4 实验结果

研究人员在随机QUBO（系数均匀采样）与MC问题QUBO（图节点数渐增）上统计“达到全局最小所需探测变量数”的概率分布。结果显示：随探测变量数增加，借助roof dual命中全局最小的概率单调上升；在n≤40的随机QUBO与MC QUBO上，所提算法平均运行时间低于暴力枚举、分支定界、迭代roof dual、QPBO与SDPA，尤其在MC问题上优势明显，因图结构使posiform交替和更易提取。

5 讨论与结论

研究人员指出，变量探测与roof dual协同可将多项式时间下界转化为精确求解器，弥补了单纯roof dual或单纯探测的不完备性。所证定理首次将2-SAT可解性判定扩展至探测语境，使算法在指数框架内具备早期停止保证。局限在于最坏复杂度仍指数，未来可结合图稀疏性选变量序。结论可表述为：对QUBO中变量集合进行探测可提高借助roof dual达到全局最小的概率；若在探测时最低roof dual界产生可解2-SAT，则该解必为全局最小；实证上该方法在随机与MC类QUBO均快于暴力枚举及若干前沿算法。