一种混合整数线性规划求解过程中的割平面选择方法及装置、标签构造方法

摘要: 本发明属于计算机优化,具体涉及一种混合整数线性规划求解过程中的割平面选择方法及装置、标签构造方法。背景技术:1、混合整数线性规划是物流调度、生产排程、网络设计、...
一种混合整数线性规划求解过程中的割平面选择方法及装置、标签构造方法

本发明属于计算机优化,具体涉及一种混合整数线性规划求解过程中的割平面选择方法及装置、标签构造方法。

背景技术:

1、混合整数线性规划是物流调度、生产排程、网络设计、芯片验证等工业场景的核心建模工具。现代 milp 求解器(如 scip、gurobi、cplex)采用分支定界框架:将原问题的线性规划(lp)松弛作为下界来源,并在求解过程中通过割平面(cutting planes)不断收紧该松弛,使对偶界(下界)与原始界(上界)尽快收拢。

2、在每一轮分离(separation round)中,各类割生成器会产生数十至上百条候选割。若全部加入 lp,会导致约束矩阵膨胀、lp 求解时间超线性上升、数值性态恶化;因此求解器需要从候选割中选择少量割加入 lp,即"割平面选择"问题。割选择的质量直接影响整条搜索轨迹的收敛速度。

3、现有技术主要有两类方案:

4、方案一:原生启发式评分。以 scip 为代表,求解器对每条候选割计算 efficacy(切割强度)、目标平行度、整数支撑度、定向割断距离等测度的加权和(下称"hybrid 分数"),再做两两正交的贪心筛选。该方案稳定鲁棒,但完全依赖人工经验规则,无法从历史求解数据中学习。

5、方案二:纯机器学习评分替换。近年研究(如 tang et al., icml 2020;huang etal., pattern recognition 2022;paulus et al., icml 2022;wang et al., iclr2023)用神经网络或树模型为候选割打分,并在预筛后以模型分数完全替换 hybrid 分数。此类方案在单一评估配置下报告了可观收益,但发明人经大量实验发现:纯学习打分器的收益对求解器的置换种子(permutation seed)高度敏感——在六个置换种子的复测中,纯学习策略的平均改进在 -0.32 至 +0.06 之间摆动,且在多数种子下劣于原生启发式;其逐例最差结果可造成求解时间数倍的退化。

6、进一步地,发明人尝试过"实例级门控"方案,即训练元模型预测某实例是否适合启用学习打分器、在预测不利的实例上回退至原生规则。然而实验表明,逐实例的收益符号在置换种子之间接近随机(跨种子符号一致率仅 52%–58%),此类"预测是否介入"的方案在原理上缺乏可学习性,多种独立实现均未奏效。

7、现有技术存在的问题:学习模型虽包含有益的割质量信号,但其噪声会直接传导至求解轨迹,导致性能不稳定;如何在利用学习信号的同时抑制其噪声,使割选择在多种求解动态下均能稳定不劣于原生启发式并获得实质改进,是本领域亟待解决的技术问题。

技术实现思路

1、本发明的目的在于针对现有技术中纯学习割打分器性能不稳定、原生启发式评分无法利用学习信号的问题,提供一种混合整数线性规划求解过程中的割平面选择方法及装置、标签构造方法,实现学习信号与原生启发式的稳健融合,提高割选择在不同求解动态下的稳定性与收益。

2、为实现上述目的,本发明的技术方案是:一种混合整数线性规划求解过程中的割平面选择方法,包括:

3、在混合整数线性规划求解器的分支定界树求解过程中,于每个求解重启周期的根节点的首个分离轮次,获取割生成器产生的候选割集合;

4、计算所述候选割集合中各候选割的第一分数和第二分数,其中,所述第一分数由求解器原生的启发式评分规则确定,所述第二分数由预先训练的机器学习模型预测得到;

5、将各候选割的第一分数和第二分数分别在候选割集合内进行归一化处理,得到归一化第一分数和归一化第二分数;

6、按预设权重α对归一化第一分数和归一化第二分数进行加权融合,得到各候选割的融合分数,所述融合分数=α×归一化第二分数+(1-α)×归一化第一分数,其中0<α<1;

7、根据融合分数对候选割集合中的候选割进行选择,并将选中的割平面加入当前线性规划松弛;

8、其中,除每个求解重启周期的根节点的首个分离轮次外的其余节点及分离轮次,由求解器原生选择器处理。

9、进一步的,所述将各候选割的第一分数和第二分数分别在候选割集合内进行归一化处理,包括:

10、采用池内min-max归一化,将分数映射至[0,1]区间,任一候选割的归一化映射值=(分数-当前候选割集合内该分数的最小值)/(当前候选割集合内该分数的最大值-该分数的最小值)。

11、进一步的,所述预设权重α的取值范围为0.4≤α≤0.6;优选地,α=0.5。

12、进一步的,在计算第一分数之前,还包括:

13、按照第一分数对候选割集合中的候选割排序,仅保留排序位于前ρ比例的候选割进入后续处理步骤,其中0<ρ<1;优选地,ρ=0.3;

14、所述第一分数为切割强度、目标平行度、整数支撑度与定向割断距离的加权和。

15、进一步的,所述根据融合分数对候选割集合中的候选割进行选择,包括:按照融合分数降序遍历候选割,仅当候选割与已选集合满足两两正交性约束时将其加入已选集合,直至达到预设的数量预算。

16、进一步的,所述机器学习模型为梯度提升树回归模型;所述机器学习模型的训练标签通过如下方式构造:

17、将每个分离轮次的线性规划目标改进量,按照各被应用割平面的切割强度占相应轮全部被应用割平面切割强度之和的比例,分摊归因至相应轮被应用的割平面;未被应用的候选割对应的训练标签置零。

18、进一步的,所述机器学习模型的输入特征包括:割平面结构特征(非零元数、边界值、常数项)、系数统计特征(范数、均值、标准差、稀疏度)、求解器内建评分(切割强度、目标平行度、定向割断距离、整数变量数)、求解器状态特征(重启轮次、节点编号、分离轮次计数)以及来源类型。

19、本发明还提供了一种用于训练割平面选择模型的标签构造方法,包括:

20、在混合整数线性规划求解器的分支定界树求解过程中,记录每个分离轮次的前后线性规划目标值以及相应轮被应用的割平面集合;

21、计算相应分离轮次的相对改进量,所述相对改进量为前后线性规划目标值之差与前目标值绝对值的比值;

22、将相对改进量按照各被应用割平面的切割强度占相应轮全部被应用割平面切割强度之和的比例,分摊至相应轮被应用的各割平面,作为训练标签;未被应用的候选割的训练标签置零;

23、对各实例的各个分离轮次重复执行上述步骤,形成训练数据集。

24、进一步的,还包括:对构造得到的训练标签在预设分位数处进行截尾处理,抑制极端标签数值。

25、本发明还提供了一种混合整数线性规划求解过程中的割平面选择装置,执行如上述所述的一种混合整数线性规划求解过程中的割平面选择方法,包括:

26、候选获取模块,用于在混合整数线性规划求解器的分支定界树求解过程中,于每个求解重启周期的根节点的首个分离轮次,获取割生成器产生的候选割集合;

27、打分模块,用于计算所述候选割集合中各候选割的第一分数和第二分数,其中,所述第一分数由求解器原生的启发式评分规则确定,所述第二分数由预先训练的机器学习模型预测得到;

28、归一化模块,用于将各候选割的第一分数和第二分数分别在所述候选割集合内进行归一化处理,得到归一化第一分数和归一化第二分数;

29、融合模块,用于按预设权重α对归一化第一分数和归一化第二分数进行加权融合,得到各候选割的融合分数,所述融合分数=α×归一化第二分数+(1-α)×归一化第一分数,其中0<α<1;

30、选择模块,用于根据融合分数对候选割集合中的候选割进行选择,并将选中的割平面加入当前线性规划松弛;

31、其中,除每个求解重启周期的根节点的首个分离轮次外的其余节点及分离轮次,由求解器原生选择器处理。

32、本发明还提供了一种计算机可读存储介质,其上存储有计算机程序,所述计算机程序被处理器执行时实现如上述所述的一种混合整数线性规划求解过程中的割平面选择方法,或实现如上述所述的一种用于训练割平面选择模型的标签构造方法。

33、相较于现有技术,本发明具有以下有益效果:

34、1、稳定性实质提升。在miplib 2017 easy测试集35个实例、6个置换种子、300s/600s双时限的实验中,本发明方法(α=0.5)对默认求解器取得174胜4负(300s)与176胜10负(600s),逐例改进的10%分位点(p10)全部非负;而纯学习打分器(α=1)在同样条件下为88胜80负(300s)、102胜83负(600s),均值为负。

35、2、收益显著且可复制。平均归一化原始-对偶积分改进为+0.332(300s)与+0.307(600s),逐种子wilcoxon符号秩检验p值低至10-9;在36个未参与训练与划分的collection大实例上复现为+0.088/+0.065。

36、3、参数容错性好。权重扫描(α∈{0.25,0.5,0.75,1.0})显示整个混合区间均为正收益,最优为单峰α=0.5,部署无需精细调参。

37、4、无需实例级决策。不依赖门控或实例过滤,避免了实例级收益预测不可学习的问题。