凝聚式层次聚类算法在露天采矿MILP数学模型中的应用实践

本文采用凝聚式层次聚类算法对块体数据进行预处理,显著降低了混合整数线性规划(MILP)数学模型在矿业应用中的复杂度,以解决矿业排产优化中的复杂问题。该方法的核心在于根据块体的地质和采矿相关属性的相似性,将大量小块体合理聚合成相对较少的大聚合单元,从而简化了模型的变量和约束条件,减少了求解优化问题所需的计算资源和时间。通过某大型露天金矿采矿联合体的应用案例研究,证明了凝聚式层次聚类算法在实践中的有效性。原始的MILP模型由于块体数量巨大和计算复杂度高无法直接求解。应用聚类算法后,将36183个块体合理减少到5810个聚合单元,显著降低了问题的规模。

基于MILP的轻量级密码算法ACE的差分分析

研究了轻量级密码算法ACE的差分性质。首先定义了n维环形与门组合,充分分析了该结构中与门之间的相互关系,仅利用O(n)个表达式给出其精确的MILP差分刻画,将ACE算法中的非线性操作转化为32维环形与门组合,从而给出了ACE算法的MILP差分模型。其次根据MILP模型求解器Gurobi的求解特点,给出了快速求解ACE的MILP差分模型的方法。对于3~6步的ACE置换,得到了最优差分链,利用多差分技术给出了更高概率的差分对应,从而给出了ACE置换为3步的认证加密算法ACE-Aε-128的差分伪造攻击与哈希算法ACE-H-256的差分碰撞攻击,成功概率为2^(-90.52),并证明了4步ACE置换达到了128bit的差分安全边界。实际上,n维环形与门组合的MILP差分刻画具有更多的应用场景,可应用于SIMON、Simeck等密码算法的分析中。

求解带有阻塞限制的HFSP的MILP模型与改进回溯搜索算法

针对带有阻塞限制的不相关并行机混合流水车间调度问题,以最小化最长完工时间为目标,依据不同的建模思想,建立了求解该问题的4个混合整数线性规划(MILP)模型;鉴于混合整数线性规划不适合求解中大规模问题,提出了一种改进的回溯搜索算法以求解中大规模问题,在该算法中,引入了轮盘赌选择策略以及变邻域搜索算法,以提高算法的收敛速度以及局部搜索能力。最后,对所提MILP模型以及算法进行了对比分析,通过对具体实例的求解验证了所提MILP模型以及算法的有效性及优越性。

基于MILP寻找SM4算法的差分特征

基于混合整数线性规划(mixed integer linear programming, MILP)的自动化搜索方法被广泛用于搜索密码算法的差分特征,已形成一套完整的框架.该框架采用的基本原理是用线性不等式来刻画密码算法的各个操作,该框架适用于搜索采用4-bit S盒的密码算法的差分特征.对于采用8-bit S盒的密码算法,基于该框架的搜索模型计算量很大,以致无法高效地找到差分特征.SM4算法于2006年由中国政府发布,于2012年成为国家密码行业标准,于2016年成为国家标准的迭代分组密码算法,其分组状态为128 b,每轮包含4个8-bit的S盒.为了高效地搜索SM4算法的差分特征,研究了对8-bit S盒进行MILP建模的问题,对于采用8-bit S盒的密码算法,改进了搜索高概率差分特征的方法.对于19轮SM4算法,不仅找到了概率为2的差分特征,而且找到了概率为2的差分特征,这是目前基于MILP建模找到的SM4算法轮数最多、概率最高的差分特征.

ACT、TED算法基于MILP搜索的积分分析

ACT和TED算法是近年来相继被提出的,分别基于SPN结构和Feistel结构而设计的两种轻量级分组密码算法.本文根据这两种算法不同的结构特性,分别构建了相关的基于比特可分性的MILP模型,并调用求解工具Gurobi对MILP模型进行求解.实验结果表明:ACT和TED算法都存在8、9、10轮积分区分器,另外TED算法还存在7轮积分区分器.根据所搜索到的积分区分器,实现了两种算法的11轮密钥恢复攻击方案.利用ACT算法的9轮积分区分器向后扩展2轮进行11轮的密钥恢复攻击时,攻击数据复杂度为2^(36.39),时间复杂度为2^(36.39)次11轮加密,存储复杂度为2^(20).利用TED算法的8轮积分区分器向后扩展3轮进行11轮的密钥恢复攻击时,数据复杂度为2^(60.81),时间复杂度为2^(109.54)次11轮加密,存储复杂度为2^(59).

基于混合整数线性规划的MORUS初始化阶段的差分分析

认证加密算法MORUS是凯撒(CAESAR)竞赛的优胜算法,抗差分分析性能是衡量认证加密算法安全性的重要指标之一。该文研究了MORUS算法初始化阶段的差分性质,首先给出了一个差分推导规则,可以快速获得一条概率较大的差分链。在此基础上利用混合整数线性规划(MILP)自动搜索技术求解更优的差分链。为了提高搜索速度,结合MORUS初始化阶段的结构特点给出了分而治之策略。根据ΔIV的重量、取值将MILP模型划分为多个子模型并证明了部分子模型的等价性,大大缩减了模型的求解时间,得到了MORUS初始化阶段1~6步状态更新的最优差分链。最后给出了简化版MORUS的差分-区分攻击,该文的结果较之前的工作有较大的提升。

基于神经区分器的KATAN48算法条件差分分析方法

针对KATAN48算法的安全性分析问题,提出了一种基于神经区分器的KATAN48算法条件差分分析方法。首先,研究了多输出差分神经区分器的基本原理,并将它应用于KATAN48算法,根据KATAN48算法的数据格式调整了深度残差神经网络的输入格式和超参数;其次,建立了KATAN48算法的混合整数线性规划(MILP)模型,并用该模型搜索了前加差分路径及相应的约束条件;最后,利用多输出差分神经区分器,至多给出了80轮KATAN48算法的实际密钥恢复攻击结果。实验结果表明,在单密钥下,KATAN48算法的实际攻击的轮数提高了10轮,可恢复的密钥比特数增加了22比特,数据复杂度和时间复杂度分别由2^(34)和2^(34)降至2^(16.39)和2^(19.68)。可见,相较于前人单密钥下的实际攻击,所提方法能够有效增加攻击轮数和可恢复的密钥比特数,同时降低攻击的计算复杂度。

地铁车站步行交通网络引导标识诱导强度设计

地铁车站具有复杂的客流走线,乘客需依靠行人引导标识完成站内走行。通过引入节点吸引度量化引导标识的诱导强度,建立双层规划模型对引导标识进行设计,以改善地铁车站行人引导标识系统,提高乘客站内走行效率。其中,上层模型以节点吸引度为决策变量,以最小化乘客总走行时间为目标;下层模型为考虑节点吸引度的UE联合出行分布/交通分配模型,描述给定节点吸引度下乘客的路径选择行为。利用模拟退火+MILP线性化的方法进行求解。算例表明,基于节点吸引度的最优化求解来进行引导标识布设,能有效减少乘客总走行时间成本,并且诱导强度不是越高越好,过度引导会使引导效果差于无标识引导。模型及算法可以为地铁车站步行交通网络引导标识系统优化提供量化参考。

基于混合整数线性规划和强化学习的微电网经济优化调度

针对微电网中可再生能源的不确定性和波动性,以及负荷的动态变化带来的复杂性问题,提出了一种将混合整数线性规划(MILP)和强化学习(RL)相结合的MILP-RL算法。首先,在算例分析中,采用粒子群优化(PSO)算法和MILP对微电网的负荷、风机、光伏预测数据进行经济调度策略求解;然后,将求解的结果作为RL的初始调度策略,构建了PSO-RL和MILP-RL两种组合算法;最后,为了模拟可再生能源的不确定性和波动性以及负荷的动态变化,在预测数据的基础上添加了扰动并采用PSO、RL及组合算法PSO-RL、MILP-RL对扰动数据进行求解。结果表明,相比PSO算法和RL,所提出的MILP-RL组合算法在应对可再生能源的不确定性和负荷的动态变化方面表现出更高的经济性和更快的收敛速度。

基于涟漪扩散算法的航空器滑行路径优化

针对当前机场场面交通拥挤、航班不正常率日益增高的现状,研究了航空器滑行路径优化问题。结合场面运行规则,提出基于真实滑行路径的多目标涟漪扩散算法以优化进离港航班的滑行路径。构建基于冲突解决的场面优化模型,以天津滨海国际机场为例进行20架航班的仿真验证,将通过广播式自动相关监视系统采集的真实路径集合与改进的涟漪扩散算法获得的帕累托最优路径集合进行比较分析。结果表明:与真实路径相比,20架航班的总滑行时间从7107.1s降至6852.1s,减少255s,总完成时间从7153.2s降至6894.1s,减少259.1s,共6架航班的滑行时间得到明显优化。通过案例仿真结果发现,通过改进的涟漪扩散算法得到的帕累托最优滑行路径以符合真实滑行规则为前提,可以有效的优化机场场面滑行路径。

低碳背景下风电与输电网综合协调投资规划模型研究

我国风电基地和负荷中心呈逆向分布,需要通过跨区输送实现异地消纳促进风电可持续发展,目前风电和输电网规划不协调的问题极为突出,提出了风电与输电网综合协调投资规划模型。首先提出了以用户费用、风电及输电网投资总成本最小为目标函数的风电与输电网投资混合整数线性规划模型(Mixed-Integer Linear Programming,MILP),以确定最优的风电投资规模以及配套输电网建设,通过改进分支定界方法对模型进行求解,通过算例分析验证所构建模型的科学性和合理性。

回收物流设施多层选址模型及其算法

针对废弃物品的收集、预处理和再制造问题,建立了回收物流设施选址混合整数规划(MILP)模型,用分枝定界法求解.为提高分枝定界法的收敛速度、减少运算量,先用遗传算法为MILP找到较好的可行解,以其对应的目标函数值为分枝界定法上界,从而可以在分枝界定法的搜索中剪去大量分枝.用算例证明了算法的有效性和可行性.

考虑分布式电源不确定性的配电网鲁棒动态重构

间歇性分布式电源并网使得配电网网络重构过程需要考虑更多的不确定因素。在利用仿射数对分布式电源出力的不确定性进行合理分析与建模基础上,建立以重构周期内开关动作耗费与网络有功损耗等综合成本最低为目标函数,以网络安全运行为约束条件的配电网鲁棒动态重构模型。为精确求解该数学模型,引入基于最佳等距思想的分段线性逼近方法将原目标函数松弛为线性可解形式,并根据对偶定理将模型进一步等效转化为双层混合整数线性规划问题;最后采用列约束生成算法对模型进行高效求解。修改的PG＆E 69节点系统测试分析结果表明,与现有的配电网确定性动态重构方法比较,所提鲁棒动态重构方法在抗系统不确定性扰动方面具有明显的优势。

供应链订单任务分配模型及其混合遗传算法

建立了面向供应链的多产品、多订单、多时段的订单任务分配的混合整数线性规划模型.为缩短求解时间和避免大量非法染色体出现,设计了基于遗传算法和启发式规则相结合的混合遗传算法.通过算例比较了该算法和SAS软件的OR模块.结果表明,与SAS/OR模块相比,该算法最优解误差为2.3%,但计算运行时间仅为SAS/OR模块的0.89%.

考虑退货不确定性的多层次多站点逆向物流网络选址优化研究

在退货量不确定情况下,为追求电商企业逆向物流网络成本最小化,建立了多层次多站点的混合整数规划模型。将目标区域进行网格化处理,通过球上距离公式计算相邻备选站点、不同层次备选点间的运输距离,使用蒙特卡罗法模拟退货量,并设计了双染色体编码的遗传算法进行求解。算例验证了模型算法的可行性,并且得出了逆向物流网络成本最小时,快递站点和退货处理中心的选址,快递站点的选址与退货量大小存在对应关系,研究客户退货量会使物流网络选址得到优化。

基于SGRASP-LP算法的混流装配线排序问题

针对实际混流装配线上工作站工作过载过大、无效时间过长导致的装配线运行效率低下问题,在保留基本模型约束条件的基础上引入“保持生产混合”和“作业自主中断”两个约束条件,建立以“最小化工作过载和无效时间”为目标的混流装配线排序问题优化模型。在基本GRASP算法的初始解构造阶段增加阈值参数选择机制,并将改进后的GRASP算法与线性规划方法结合,设计了模型的SGRASP-LP求解算法。以某汽车企业的底盘装配线为例,将SGRASP-LP算法分别与GRASP算法和企业解决该类问题常用的MILP算法相比较。结果表明,SGRASP-LP算法运算速度更快,所求方案更优,是解决相关排序问题的有效算法。

动态环境下混合生产的Makespan调度方法

针对动态生产环境下混合生产的最小完工时间 ( Makespan)调度问题 ,借鉴于预测控制的思想 ,用滚动优化的原理求解 .提出可操作集的概念 ,将动态环境下的调度问题合理分解 ,并将所得的子问题规范化 ,并给出适用小规模问题的基于混合整数规划的算法 ,对于较大规模的问题给出快速收敛的启发式算法 .仿真算例表明方法的可行性 .

调整时间与顺序相关的flowshop调度的精确算法

调整时间与顺序相关的流水车间调度问题 (flowshop scheduling with sequence dependent setup times,FSSDST)在过程制造业中有着广泛的应用背景 ,是一类比较复杂的调度问题 .对目标函数是最小化最大流程时间 (makespan)的同排列流水车间 FSSDST调度问题进行了研究 ,建立了 FSSDST的混合整数线性规划模型 (MIL P) ,提出了两种确定原问题的下界方法 :(1)按照第 m台机器 (最后一台机器 )定界 ;(2 )按照全部机器定界 .根据这两个下界 ,提出并实现了分支定界算法 .为了提高分支定界算法的效率 ,提出了两种改进上界的策略 :(1)改进初始上界法 ;(2 )改进动态上界法 .实现了上述所有算法 。

Benders计算机程序库的开发及其在环境规划中的应用

混合整变量线性规划模型在国外许多行业和我国环境规划领域得到广泛应用。Benders分解算法是求解大规模混合整变量线性规划问题的一种先进技术,该技术在国外求解运输问题和网络问题范畴的实际问题得到了成功。我们应用Benders技术研制开发了大型计算机软伴;这是在我国系统工程领域和国际环境规划工作中的首次应用。在程序库开发工作中,引进和采用了当今国际上先进的运筹学方法和计算机技术。程序库在求解实际的环境规划问题中获得了初步的成功。我们应用所开发的程序库和数学模型求解了一个具有635个约束条件,1087个变量(其中0—1整变量为126个)的实际城市综合整冶规划问题。这是至今国内所求解的最大规模的混合整变量线性规划问题,也是国际上用Benders方法求解的最大的环境规划问题。

非方阵指派问题的求解

本文将2类方阵指派问题——极大极小和总体极小指派问题——的矩阵作业解法推广到非方阵情形,即求解任务与人员数目不等的指派问题,且维持矩阵作业法的效率.假定m>n,则按本文行优先选取算法求解m×n非方阵指派问题的最大逻辑运算量为O(mn2),其效率通常与执行一轮覆盖的矩阵作业法相当.