Page 408 - 《软件学报》2024年第4期

1986 软件学报 2024 年第 35 卷第 4 期

w(u) = w(v),L ZR ,L HZ , 至此, 动态选取策略构建 MILP 模型的过程结束. 值得注意的是, 在上述动态选取过程中
取
我们将输入可分性汉明重量分为 3 类: {0,n},Θ ZR ,Θ HZ , 事实上, 在集合 Θ ZR 中, 每个汉明重量对应的不等式数量
较少, 但集合中所有元素的不等式求和的数量依旧比较大, 因此我们可以对集合 Θ ZR 进行再次分类, 只需将向量 a
n+1 个点进行相应的更改即可. 例如: 将输入可分性汉明重量分类情况由 3 种情况更改为 r 种情况, 即
的维数与
,a
,a
向量 a 的扩充维数由 3 维改为 r 维, 此时 Θ ZR 分为 r−2 部分: Θ ZR 0 ,Θ ZR 1 ,...,Θ ZR r−3 , 同时 (a ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 ⌊ log 2 n⌋ +3 )
a ′ ,a ′ ,...,a ′ a ′ =a , a ′ =a , a ′ ,a ′ ,...,a ′
更改为 , 其中 ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 而
⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 ⌊ log 2 n⌋ +r ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +r ⌊ log 2 n⌋ +2 ⌊ log 2 n⌋ +3 ⌊ log 2 n⌋ +r−1
(1,0,...,0) (0,1,...,0) (0,0,...,1) . 下面将通过一个例子介绍基于动
的取值则根据新的 Θ ZR 的分类情况分别取 , ,
态选取策略构建线性层可分性传播 MILP 模型的具体过程.
例 1: 假设矩阵 M ∈ F 8×8 , 记其输入可分性 u = (u 0 , u 1 ,...,u 7 ) ∈ F , 输出可分性 v = (v 0 , v 1 ,...,v 7 ) ∈ F . 通过如下
8
8
2 2 2
3 个步骤可构建该矩阵可分性传播的 MILP 模型.
M 输入可分性的汉明重量 wt(u)∈{0,1,…,8}. 对 wt(u) 的上述所有情况, 我们用
● 汉明重量的点集刻画: 矩阵
4 维向量 a=(a 0 , a 1 , a 2 , a 3 )∈{(0, 0, 0, 0), (0, 0, 0, 1),…, (1, 0, 0, 0)} 刻画矩阵 M 输入可分性汉明重量的所有情况, 其
中 wt(u)=8a 0 +4a 1 +2a 2 +a 3 .
● 动态选取汉明重量: 将向量 a 的维数扩充 6 维: (a 0 , a 1 ,…, a 9 ), 其中 a 4 , a 5 ,…, a 9 的取值表示输入可分性汉明
重量的分类情况, 例如下面的集合 D 的分类情况为: {0,n} = {0,8} Θ ZR = {1,2,6,7},Θ HZ = {3,4,5} , 并将 Θ ZR 继续
,
分为 4 D 的动态选取规则为: 当 wt(u) 为 0
个部分
Θ ZR 0 = {1},Θ ZR 1 = {2},Θ ZR 2 = {6},Θ ZR 3 = {7} , 此时集合 a 4 = 1 时,
或 8; 当 a 5 = 1 时, wt(u) 为 1; 当 a 6 = 1 时, wt(u) 为 2; 当 a 7 = 1 时, wt(u) 为 6; 当 a 8 = 1 时, wt(u) 为 7; 当 a 9 = 1 时,
wt(u) 为 4 或 5 或 6. 最后用 (a 0 ,a 1 ,...,a 9 ) 的约束不等式集 L wt 刻画集合 D .

 −a 4 −a 5 −a 6 −a 8 −a 9 ⩾ −1

  
 (0,0,0,0,1,0,0,0,0,0)  
 −a 0 +a 4 ⩾ 0


 
 
 
   −a 3 +a 5 +a 8 +a 9 ⩾ 0
 (0,0,0,1,0,1,0,0,0,0)


 
 
 
 
 


 (0,0,1,0,0,0,1,0,0,0) −a 2 +a 3 −a 4 −2a 5 −a 8 −a 9 ⩾ −1
 
 
 
 

  a 2 −a 7 ⩾ 0

 (0,0,1,1,0,0,0,0,0,1)  

 
 
 
 a 2 +a 4 +a 5 +a 9 ⩾ 1


 
D =  (0,1,0,0,0,0,0,0,0,1) , L wt =  .

  −a 1 +a 7 +a 8 +a 9 ⩾ 0

 
  

 (0,1,0,1,0,0,0,0,0,1)  


 a 1 +a 4 +a 5 +a 6 +a 9 ⩾ 1

 
 
  
 (0,1,1,0,0,0,0,1,0,0)  −a 3 −a 7 ⩾ −1



 
 
 
 
  a 1 +a 2 −a 9 ⩾ 0
 (0,1,1,1,0,0,0,0,1,0) 



 
 
 
  −a 6 −a 7 ⩾ −1


(1,0,0,0,1,0,0,0,0,0)  
 


 −a 1 −a 2 −a 9 ⩾ −2
M 输入可分性汉明重量的某种分类情况. 考
● Indicator 约束建模: 根据上一步可知, a i = 1 (4 ⩽ i ⩽ 9) 对应矩阵
虑到 Indicator 约束的一般形式 z = f → L , 其中 f ∈ {0,1} . 因此可以添加如下约束刻画矩阵 M 的可分性传播.

a 4 = 1 → w(u) = w(v)






a 5 = 1 → L ZR 1






a 6 = 1 → L ZR 2

.
L Indicator = 


 a 7 = 1 → L ZR 6






 a 8 = 1 → L ZR 7





a 9 = 1 → L HZ
i (i ∈ {1, 2, 6, 7}) 的可分性传播使用的不等式, 具体可参照模
其中, 表示利用 ZR 方法刻画输入汉明重量为
L ZR i
型 3 与文献 [10], L HZ 表示利用 HZ 方法构建可分性传播的不等式, 具体可参照模型 1、模型 2 与文献 [9].
根据上述 3 个步骤, 通过不等式集合 L = {8a 0 +4a 1 +2a 2 +a 3 = wt(u),L wt ,L Indicator } 作为约束条件, 可以构建更
加精确的线性层可分性传播的 MILP 模型. 该技术的建模过程如算法 1 所示.