基于拉格朗日乘数法的可分离混合二值二次规划求解：无需连续变量离散化的QUBO采样方法

《Scientific Reports》：QUBO sampling for mixed binary quadratic programming without continuous variable binarization

　　

摘要

量子退火及相关组合优化方法通常以二次无约束二值优化（QUBO）问题作为输入，而许多实际模型包含约束条件和连续变量。标准的QUBO转换需要对连续变量进行离散化，从而增加二值维度，并使可行低能态更难以采样。我们开发了一种针对可分离的混合二值二次规划类（MBQPs）的拉格朗日乘数方法，无需对连续变量进行离散化。该方法基于有限温度自由能公式，并使用QUBO采样处理二值部分。在固定的拉格朗日乘数下，连续部分可解析地积出，仅参与乘数更新，从而保持QUBO在原始二值变量上的形式。我们在二次p-中位点问题的连续松弛上进行评估。与基于罚函数的QUBO公式相比，该方法能更可靠地生成可行解。在合适的逆温度下，其条件相对误差对于小规模实例与局部搜索相当，对于较大规模的测试实例通常更低。在达到目标的时间对比中，该方法对于严格的固定精度目标保持了较高的达标率。对于测试范围内的较大规模实例，它还比商业混合整数优化求解器更快地达到规定目标。