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

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

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

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

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

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

基于分层分枝定界算法的机组组合

针对常规机组组合算法计算量大、计算精度不高的问题,提出了一种分层分枝定界算法。该算法采用分层求解策略,对传统机组组合模型进行线性化处理,进而基于线性规划算法求解松弛整数变量的线性化机组组合模型,通过取整策略形成初始分枝,作为分枝定界算法的上层;采用经典广度优先搜索算法的节点搜索策略,以及考虑负荷备用和机组启停时间约束并结合最大、最小边界的分枝策略,不断进行分枝、定界和剪枝获得下层问题的最优解。不同测试算例分析表明,所提出的分层分枝定界算法快速、稳定,能够考虑机组爬坡约束,可以在保证合理计算时间内有效提高求解精度。

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

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

混合物定性定量分析的分枝定界算法

巳知被测体系可能存在的物种范围,但其确含何种物质及相应浓度必须经分析方可确定,实为分析化学实践中常见的一类分析体系。基于分枝定界原理,本文提出一种可直接对其进行定性定量解析的光谱多元分析算法,可显著减少计算量,却无丢失真实信息的风险。对实际紫外可见及荧光混合物光谱进行解析,均获满意结果。

非凸二次规划全局极小问题的新型分枝定界算法

针对求解多面集上二次函数的全局近似最优解问题,利用逐步缩小对偶间隙的处理办法,提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。

弱有效集上凹函数极大问题的分枝定界算法

弱有效(有效)集上的优化是处理多目标线性规划的一种重要途径。考虑了弱有效集上凹函数的极大问题。这个优化问题主要有两方面的困难:一方面,弱有效集一般说来不再是凸集;另一方面,该问题不属于存在一个全局最优解在多面体集的一个极点处取得的一类问题。因此,提出的方法的主要思想是:问题首先被转化为Rk+1空间中一个特殊全局优化问题;其次,对这个问题建立了一个分枝定界型算法。算法的分枝过程采用锥形剖分,定界过程通过求解普通的线性规划实现;最后,对算法的收敛性进行了分析。

具有任务资源需求分布与资源时变约束的RCPSP分枝定界算法

研究资源受限项目调度问题，考虑了项目中每个任务对可更新（再生）资源需求的任意分布、可更新（再生）资源的最大供给量随时间而变化的情形。作为对前人研究结果的进一步推广，利用了分枝定界技术，以及事件驱动的时间增量方式。

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

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

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

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

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

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

分支与定界算法的实现研究

本文介绍分支与定界算法的基本原理 ,着重讨论了此算法在具体实现过程中遇到的两个难点

单件车间关键工序调度问题的定界算法

提出了一种以“定界权值”为主要参数的求解有交货期的单件车间生产调度问题的定界算法。引入“关键工序定界权值、非关键工序定界权值”的概念,并依据“关键工序排序加工,非关键工序即刻加工”的构想,确定工件各工序的加工时间范围,并根据计算结果编制机台作业计划。当关键工序加工时间发生冲突时,修正其定界权值,重新计算其加工时间范围。该方法简化问题,运算速度提高。

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

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

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

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

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

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

一类单调非凸约束最优规划修正的新型分枝定界算法

本文讨论了一类单调非凸约束最优规划的目标函数和约束集的结构特征性质.阐明了如何将所考虑的问题等价地转化为一个递增函数在另一个递增函数水平集上的极大优化问题.在此基础上提出了一个我们称之为修正的新型分枝定界算法.新算法的修正之处是在计算新的极点时,采用了一个有效的新的区域删除模式以构造越来越小的Polyblock集覆盖EnH且不含y,以排除问题(P)可行域中不存在全局ε-最优解的部分.最后,证明了算法的收敛性.初步的数值实验表明算法是有效可行的,可应用于求解更广的一类非凸最优规划.

带有二次约束的二次规划问题的一个收缩分枝定界算法

通过解线性规划问题,寻找包含原问题可行域的超矩形,利用剖分技术对这个超矩形进行分枝和收缩以减少算法的迭代次数,从而用线性规划松弛方法来确定原问题在每个小超矩形上的最优值的下界,提出一种新的带有二次约束的二次规划问题的收缩分枝定界算法,并证明了该算法是收敛的.

分枝定界算法在食品分析中的应用──水果中有机酸的同时定性定量分析

将电位滴定法与分枝定界算法相结合：研究测定了水果中有机酸的组成及含量，结果与文献基本一致。对已知类型（如某一类水果）的样品，本方法不必预先进行定性分析，一次测定即可同时完成定性和定量工作。