面向交通流预测的分支定界算法图卷积模型

为对交通流进行准确预测,提出一种将图优化与预测相结合,在单管路中面向交通流的时空混合图卷积预测模型,用于边缘环境下物联网的城市交通流预测。首先对关联图进行预处理,以去除城市交通数据原始道路网中的噪声;再用LOF删除不相关的模型和噪声;最后将得到的图扩展成图卷积神经网络,估算城市的交通流。另外,采用基于分支定界的优化技术对超参数进行精确调整。结果表明:所提模型在交通流预测方面效果更优,当图中节点数较多时,预测的精准性明显优于其他基准模型。

同尺寸矩形毛坯排样的连分数分支定界算法

在确定同尺寸矩形毛坯最优排样方式的算法中 ,连分数算法的时间效率最高 ,但所生成排样方式的切割工艺复杂 提出连分数分支定界算法 ,该算法应用连分数法确定毛坯数最优值 ,采用贴切的上界估计方法 ;在搜索过程中只保留上界不小于最优值的分支 ,遇到下界等于最优值的分支时结束搜索 实验结果表明 ,该算法的时间效率和连分数算法接近 ,并可以有效地简化切割工艺 ,生成切割工艺最简单的排样方式 最后 。

基于多信号流图与分支定界算法的故障诊断

针对实时在线故障诊断问题,提出了一种基于多信号流图和分支定界算法的故障诊断方法。通过建立多信号流图模型生成相关矩阵作为诊断知识,进而由相关矩阵以及观测向量产生冲突集,使最小诊断集的求解过程映射为整数规划问题;采用分支定界算法,通过对冲突集的分支、定界以及剪支得到故障诊断的最优解,从而避免了穷举问题造成的搜索"爆炸"。以某型机载燃油系统为对象对本文提出的算法进行了验证。结果表明:本文算法与常用的多信号流图诊断推理算法TEAMS-RT相比,算法速度相当,故障定位精度更高,很好地涵盖单故障以及多故障组合,可以胜任大规模复杂系统的故障诊断。

整数线性规划的改进分支定界算法

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素。提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现。数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显。

求解课程表问题的分支定界算法

本文通过对中学排课程表问题的特征分析 ,给出了基于分支定界法的优化算法 ,数值试验表明这是解决一般编排中学课程表问题的有效算法。

分支定界算法在调度问题上的应用

以在ｎ台机器上串行加工ｍ个工件为例，讨论调度问题的最优求解方法，在分支定界算法中利用串行加工原理选取下界函数，在得到一个可能解后，通过回潮来取得最优解，从而揭示分枝定界算法在调度问题上的应用．

求解阻塞混流生产机器人制造单元调度问题的分支定界算法

针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明:工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。

求解线性比式和问题的缩减分支定界算法（英文）

本文针对线性比式和问题给出一个缩减分支定界算法.在算法中,基于比式分母的输出空间,我们提出一个新的范围缩减方法.结合分支定界框架和输出空间范围缩减方法,建立一个缩减分支定界算法.并给出算法的收敛性,数值实验结果展示了本文算法的优点.

基于分支定界算法的DS-CDMA UWB系统多用户检测技术研究

研究一种带预处理的检测器,利用预处理动态设定的门限值直接判决用户的比特数据信息,用以解决线性多用户检测器由于判决门限值固定而影响检测性能的问题;利用分支定界算法进行预处理可以得到全局最优解,将原有的多用户检测问题转变成较小规模的检测问题,以达到减少多址干扰、增加正确判决的概率以及降低系统检测误码率的目的.仿真实验结果表明:预处理后,系统检测正确判决的概率增大,误码率降低.

分支定界算法在白细胞特征选择中的应用研究

提出了一种基于分支定界算法的白细胞图像特征选择方法 ,该方法可有效降低特征空间的维数 ,加速分类器的速度。为验证方法的有效性 ,分别用 10 6个原始特征和从 10 6个特征中选择 3 5个最优特征进行分类实验。结果表明 ,两种情况的分类效果无明显改变 。

基于eM-Plant和分支定界算法的动态加工车间送料路径仿真与优化

利用了优秀的仿真软件和经典的优化算法理论,对现实中的动态车间送料路径进行仿真优化,并给出了结果。

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。

基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法

提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先,把原问题目标函数进行D.C.分解(分解为两个凸函数之差),利用次梯度方法,求出其线性下界逼近函数的一个最优值,也即原问题的一个下界.然后,利用全局椭球算法获得原问题的一个上界,并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后,理论上证明了算法的收敛性,数值算例表明算法是有效可行的.

分支定界算法的分布并行化研究

介绍了一种专用于计算分支定界算法的机群计算平台,其中所使用的分布并行策略减少了分支定界算法计算时间复杂度,减小了问题的规模;可以把计算平台机群中的任何一台计算机上计算出的当前全局最佳本分值,实时地广播给所有其他并行的计算机,并作为它们新的最佳本分值,实现分支节点的快速并行淘汰;应用启发式算法修改了分支定界算法,提高了分支节点的淘汰效率。选用旅行商问题实例作为测试基准。计算表明,在保证求得最优解的前提下,该平台能很好地提高分支定界算法的效率。

分支定界算法优化一维下料问题

一维下料问题是生产实践中常见的问题,优化下料要求最大限度地节约原材料,提高原材料的利用率。本文提出分支定界算法优化一维下料问题,并用MATLAB编写程序,通过计算机来完成这一复杂的过程。

地区电网无功分区分层控制中的组合分支定界算法

提出了无功功率分层控制的优化模型,该模型以变电站的无功功率偏差最小为目标函数,满足无功功率平衡及功率因数限制等不等式约束,并采用组合分支定界算法进行求解.实际应用表明,采用该方法不仅可以实现无功功率的就地平衡,还可以实现无功功率不同电压等级之间分层的支持决策,验证了该方法的有效性.

一类非线性比式和问题的分支定界算法

针对一类带有常系数的非线性比式和全局优化问题(P),给出求解该问题的分支定界算法.首先,将问题(P)转化为问题(Q),两者的变量个数和约束条件的个数相同.然后,利用不等式放缩的方法,建立问题(Q)的松弛线性规划,并结合分支定界算法求解.最后,在此基础上提出区域删减策略,并进行数值实验.结果表明:本算法和删减策略均是有效的.

基于分支定界算法的护士排班模型研究

针对国内缺乏通用排班模型和排班技术落后的问题,通过调研分析建立了带有强、弱约束的护士排班模型。并采用整数规划的分支定界算法对模型进行求解和分析。实例验证了该模型的有效性和可行性,有利于提高护理工作的积极性。

工件具有入树约束的同类机排序问题的分支定界算法

研究具有入树约束的两台同类机排序问题,工件具有不同的到达时间且具有单位的加工时间,目标为极小化最大完工时间.对于该NP-难问题,首先设计了一个分支定界算法并证明了算法的最优性.然后通过一个具体算例,详细验证了算法的执行过程.

基于自行车共享系统静态再平衡问题的分支定界算法

自行车共享系统是一种交通系统,允许用户在分散在城市各处的众多自动租车点之一租用一辆自行车,使用它们进行短途旅行,并在任何站点返回。良好的服务质量是建立在再平衡操作基础上完成的,具体形式表现在将自行车从一些车站移走,并将它们转移到其他车站。为了提高服务质量,研究了静态情况下的再平衡车辆路径问题,即车辆在各车站之间进行往返,以将其返回到所期望的站点,而且每一个站只能访问一次。这个问题类似于有额外限制出行的推销员的问题。其目的是找到一种最优的车辆调度方法,使车站在不平衡状态下的总等待时间最小化。首先建立相关模型,提出使用下界和上界。这些边界用于分支定界算法进行计算,得出最优解。为了验证方法可行性,对大量实例进行了计算实验,得到的结果表明了该方法的有效性。