5.1 适配参数精度（8bit整数）

教程二：建模时对问题数据进行规整化

在解决组合优化问题时，QUBO模型是一种常见的建模方式，然而高精度的系数矩阵可能超出硬件的处理能力。除了使用SDK降精度方法之外，也可以通过取整等技巧，对输入矩阵提前进行手动处理，使输入更满足具体问题的需求。通过减少建模时问题数据的小数位或直接取整，可以降低矩阵的精度，使数据更规整，同时尽量保持优化问题的最优解不变或影响较小。本教程将以一个匹配问题为例，详细介绍如何通过减少小数位和取整来降低系数矩阵精度，并分析其对目标函数和约束区域的影响。

1. 问题介绍：匹配问题

匹配问题是一种经典的组合优化问题，目标是将一组元素（例如工人）与另一组元素（例如任务）进行一一匹配，使得总成本最小化。假设我们有$n$个工人和$n$个任务，每个工人$i$执行任务$j$的成本用$C_{ij}$表示，成本矩阵$C$是一个$n\times n$的矩阵。我们需要找到一个匹配方案，使得每个工人恰好分配到一个任务，每个任务恰好分配给一个工人，同时总成本$\sum _{i,j}{C}_{ij}{x}_{ij}$最小，其中$x_{ij}$是二元变量，表示工人 $i$ 是否分配到任务$j$（1表示分配，0表示不分配）。

2. 数学模型

将匹配问题转化为QUBO模型：

（1）目标函数最小化总成本：

$$H_{\text{obj}}=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}{C}_{ij}{x}_{ij}$$

（2）约束条件：

• 每个工人$i$只能分配到一个任务：$\sum _{j=0}^{n-1}{x}_{ij}=1,\mathrm{\forall }i$

• 每个任务$j$只能分配给一个工人：$\sum _{i=0}^{n-1}{x}_{ij}=1,\mathrm{\forall }j$

这些约束通过惩罚项加入到QUBO模型中，当成本矩阵$C$中的值包含小数时，生成的QUBO矩阵和后续的Ising矩阵可能具有较高精度（即需要更多位宽来表示系数），通过减少小数位或取整，可以降低矩阵精度，同时分析其对解的影响。

2.1 降低系数矩阵精度的思路

降低系数矩阵精度的核心思想是通过简化输入数据（如成本矩阵）来减少矩阵元素的数值范围和复杂度，具体步骤如下：

（1）减少小数位：将成本矩阵中的值限制到较少的小数位（如1位小数），使数据更规整；

（2）取整：将成本矩阵中的值直接取整，进一步降低精度；

（3）影响分析：

• 目标函数：取整会改变目标函数的数值，但由于改变幅度较小（通常在±0.5以内），最优解可能保持不变；
• 约束区域：约束条件仅依赖于$x_{ij}$的取值（0或1），与成本矩阵的数值无关，因此不受取整影响。

这种方法的好处是：

• 数据规整化降低了矩阵的位宽需求，便于硬件实现；
• 最优解的稳定性通常能够保持，尤其是当原始数据的小数部分对解的区分度影响较小时。

2.2 模型公式

我们将匹配问题转化为QUBO模型，最终目标是最小化以下哈密顿量：

$$H=H_{\text{obj}}+H_{\text{constraints}}$$

其中：

• 目标函数：$H_{\text{obj}}=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}{C}_{ij}{x}_{ij}$
• 约束惩罚项（使用拉格朗日乘子法）：$H_{\text{constraints}}=P\sum _{i=0}^{n-1}{(\sum _{j=0}^{n-1}{x}_{ij}-1)}^2+P\sum _{j=0}^{n-1}{(\sum _{i=0}^{n-1}{x}_{ij}-1)}^2$

其中$P$是惩罚系数，用于确保约束的严格性。

当$C_{ij}$包含小数时，$H$的系数具有较高精度，通过取整$C_{ij}$，系数精度降低，但约束项的形式和解空间保持不变。

2.3 代码实现

以下是一个完整的Python实现，使用numpy和kaiwu库来构建QUBO模型，并计算原始和取整后的Ising矩阵精度。

import numpy as np
import kaiwu as kw

def calculate_ising_matrix_precision(cost_matrix, bit_width=14):
    """
    计算基于输入成本矩阵生成的 Ising 矩阵精度。
    
    参数：
    cost_matrix (np.ndarray): 输入的成本矩阵。
    bit_width (int): 目标比特宽度，默认为 14 位。
    
    返回：
    precision (int): Ising 矩阵的精度（位宽）。
    """
    # 获取匹配问题的维度
    n = cost_matrix.shape[0]

    # 创建 QUBO 变量
    x = kw.qubo.ndarray((n, n), "x", kw.qubo.Binary)

    # 创建 QUBO 模型
    qubo_model = kw.qubo.QuboModel()
    qubo_model.set_objective(kw.qubo.quicksum([cost_matrix[i, j] * x[i, j] 
                                               for i in range(n) for j in range(n)]))

    # 添加约束：每行和每列的和均为 1
    for i in range(n):
        qubo_model.add_constraint(kw.qubo.quicksum([x[i, j] for j in range(n)]) == 1, 
                                 f"row_cons_{i}", penalty=10)
    for j in range(n):
        qubo_model.add_constraint(kw.qubo.quicksum([x[i, j] for i in range(n)]) == 1, 
                                 f"col_cons_{j}", penalty=10)
    
    # 转换为 Ising 模型
    ising_model = qubo_model.to_ising_model()
    ising_matrix = ising_model.get_ising()['ising']
    
    # 计算 Ising 矩阵的位宽
    precision = kw.cim.calculate_ising_matrix_bit_width(ising_matrix, bit_width)
    
    return precision

# 测试示例
# 示例成本矩阵（包含小数）
cost_matrix = np.array([[18.1, 112.3, 110.2, 115.4],
                        [113.7, 17.9, 19.5, 114.1],
                        [111.2, 19.8, 15.3, 110.6],
                        [112.8, 18.3, 14.4, 16.7]])

# 计算原始成本矩阵的 Ising 矩阵精度
precision_original = calculate_ising_matrix_precision(cost_matrix)
print("Ising matrix precision (original):", precision_original)

# 对成本矩阵取整
cost_matrix_rounded = np.round(cost_matrix)

# 计算取整后的 Ising 矩阵精度
precision_rounded = calculate_ising_matrix_precision(cost_matrix_rounded)
print("Ising matrix precision (rounded):", precision_rounded)

• 原始矩阵：包含小数（如18.1、112.3），需要12位来表示Ising矩阵的系数；
• 取整后矩阵：所有值变为整数（如18、112），精度降低到8位。

取整后矩阵精度显著下降，且由于成本矩阵的变化幅度较小（每个元素最多变化 ±0.5），最优解通常保持一致。

2.4 取整的影响

（1）对目标函数的影响：

• 原始目标函数：$H_{\text{obj}}=18.1x_{00}+112.3x_{01}+\dots$
• 取整后目标函数：$H_{\text{obj}}=18x_{00}+112x_{01}+\dots$
• 变化幅度较小，通常不会改变$x_{ij}$的最优配置。

（2）对约束区域的影响：

• 约束条件仅依赖于$x_{ij}$的和（如$\sum _j{x}_{ij}=1$），与$C_{ij}$的具体值无关，因此取整不影响可行解空间。

2.5 适用场景

这种方法适用于：

• 成本矩阵中数值范围较大，但小数部分对解的区分度较低的情况；
• 需要在硬件上实现QUBO模型，且硬件对精度有限制的情况。

3. 总结

通过减少小数位或取整，可以有效降低QUBO和Ising模型的系数矩阵精度，使数据更规整，同时保持约束区域不变。虽然目标函数的数值会发生变化，但由于变化幅度小，最优解通常不受影响或影响较小。本教程以匹配问题为例，展示了如何通过代码实现这一过程，并分析其效果，在实际应用中，可以根据具体问题的特性和硬件需求调整取整策略，进一步优化计算效率和解的质量。