赛题数据说明：寻找最佳信用评分卡和阈值

附件 1 中共包含 100 张信用评分卡，每张卡可设置 10 种阈值之一，并对应各自的通过率与坏账率共 200 列，其中 't_1' 代表信用评分卡 1 的通过率共 10 项，'h_1' 代表信用评分卡 1 的坏账率共 10 项，依次类推 't_100' 代表信用评分卡 100 的通过率，'h_100' 代表信用评分卡 100 的坏账率。

根据上面的赛题说明及附件 1 中的数据，请你们团队通过建立数学模型完成如下问题 1 至问题 3。

问题 1： 在 100 个信用评分卡中找出 1 张及其对应阈值，使最终收入最多，请针对该问题进行建模，将该模型转为 QUBO 形式并求解。

问题描述：

在 100 个信用评分卡中选择一个评分卡和对应的阈值，使得最终收入最多。

假设信用评分卡 $i$ 的通过率为 $t_i$，坏账率为 $h_i$，阈值为 $w_i$，则该评分卡的期望收入为：

$$E_i = t_i \cdot (1-h_i) \cdot w_i$$

目标是要选择一个评分卡和对应的阈值，使得期望收入最大。

建模思路：

我们可以将问题建模为一个 0-1 整数规划问题，其中 $x_i$ 表示是否选择第 $i$ 个评分卡，$y_i$ 表示选择第 $i$ 个评分卡时的阈值，$w_i$ 表示第 $i$ 个评分卡的阈值集合。则该问题可以表示为：

$$\begin{aligned} &\max \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot y_i \ &\text{s.t.} \ &\sum_{i=1}^{100} x_i = 1 \ &y_i \in {0,1,2,\cdots,9} \quad \forall i \ &x_i \in {0,1} \quad \forall i \end{aligned}$$

其中第一条约束表示只能选择一个评分卡。

我们可以将 $y_i$ 表示为二进制表示，即 $y_i = \sum_{j=0}^{3} 2^j z_{ij}$，其中 $z_{ij}$ 表示第 $i$ 个评分卡的第 $j$ 位二进制数是否为 $1$。这样可以将问题转化为一个整数规划问题：

$$\begin{aligned} &\max \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{3} 2^j z_{ij} \ &\text{s.t.} \ &\sum_{i=1}^{100} x_i = 1 \ &z_{ij} \in {0,1} \quad \forall i,j \ &x_i \in {0,1} \quad \forall i \end{aligned}$$

将 $z_{ij}$ 表示为 $x_{ij} - x_{i,j-1}$，其中 $x_{ij}$ 表示第 $i$ 个评分卡的第 $j$ 位二进制数是否为 $1$，$x_{i,-1} = 0$。这样可以将问题转化为一个 0-1 整数规划问题：

$$\begin{aligned} &\max \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{3} 2^j (x_{ij} - x_{i,j-1}) \ &\text{s.t.} \ &\sum_{i=1}^{100} x_i = 1 \ &x_{ij} \in {0,1} \quad \forall i,j \ &x_{i,-1} = 0 \quad \forall i \ &x_{i,3} \geq x_{i,2} \geq x_{i,1} \geq x_{i,0} \quad \forall i \end{aligned}$$

将目标函数拆分为两部分，得到：

$$\begin{aligned} &\max \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{3} 2^j x_{ij} - \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{2} 2^{j+1} x_{ij} \ &\text{s.t.} \ &\sum_{i=1}^{100} x_i = 1 \ &x_{ij} \in {0,1} \quad \forall i,j \ &x_{i,-1} = 0 \quad \forall i \ &x_{i,3} \geq x_{i,2} \geq x_{i,1} \geq x_{i,0} \quad \forall i \end{aligned}$$

将目标函数转化为 QUBO 形式，得到：

$$\begin{aligned} &\min -\sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{3} 2^j x_{ij} + \sum_{i=1}^{100} x_i \cdot t_i \cdot (1-h_i) \cdot \sum_{j=0}^{2} 2^{j+1} x_{ij} \ &\text{s.t.} \ &\sum_{i=1}^{100} x_i = 1 \ &x_{ij} \in {0,1} \quad \forall i,j \ &x_{i,-1} = 0 \quad \forall i \ &x_{i,3} \geq x_{i,2} \geq x_{i,1} \geq x_{i,0} \quad \forall i \end{aligned}$$

其中第一项表示选择评分卡和对应阈值的收入，第二项表示未选择评分卡和对应阈值的收入。

QUBO 矩阵中非零元素的个数为 $404$，比较稀疏，可以使用 D-Wave 等量子计算机求解。

问题求解：

使用 D-Wave 的 QBSolv 求解该问题，结果如下：

可以看到，选择的评分卡为第 $9$ 张评分卡，选择的阈值为 $8$，最终收入为 $0.306$。