分支定界

摘要： 本文提出一种基于输出空间分支定界算法(OSBBA)求解一类广义线性乘积和规划问题(GLMP)的ε全局最优解.通过对问题(GLMP)的非线性等价问题(EGGP)的约束条件采用两种不同的松弛方法,得到相应的线性松弛问题(GLRP).再利用算法(OSBBA)在输出空间不断地分支来迭代求解问题(GLRP),直至逼近问题(EGGP)的ε全局最优解.同时,算法(OSBBA)的收敛性证明和计算复杂度分析表明该算法在理论上是有限迭代终止的.最后,数值实验验证并分析了算法的有效可行性.

摘要： 针对现有可持续供应链网络中指标陈旧,且未能充分利用最新可持续指标对网络进行准确衡量与优化的问题,基于《CITI评价指南7.0》,提出一种将经济成本、合规整改与节能减排、绿色供应链、推动公众绿色选择、供应链沟通与透明5项指标进行层次分析加权整合的五位一体可持续闭环供应链网络模型,并设计了一种采用蒙特卡洛树搜索改进的分支定界算法MCTS_BB进行高效求解。首先,对5项指标按相互关联影响及隶属度关系进行归一化并构造多目标决策矩阵。然后,使用决策矩阵中最大特征值对应的特征向量对多目标函数进行线性组合,建立混合整数线性规划模型。最后,通过MCTS_BB中的分支选择、随机模拟搜索和剪枝策略求解模型。通过不同规模算例验证了模型和算法的有效性,实验结果表明,五位一体模型实现了多目标函数间的有效最优平衡,为各层级决策者对模型指标与参数进行统筹管理提供决策指导。

摘要： 大规模多输入多输出(multi-input multi-output,MIMO)系统中,随着天线数量的增多,现有传统信号检测算法在高阶调制时不能很好地平衡系统的检测性能和算法复杂度。为了解决以上问题,基于二次规划(quadratic programming,QP)检测器应用了有效集法和具有可变二分法的深度优先分支定界算法,提出了一种适用于大规模MIMO高阶调制系统的低复杂度检测算法,并提出了一种修剪策略和引入了近似因子,改善了系统性能,在复杂度和性能之间进行了更好地折中。复杂度分析表明,所提出算法复杂度比QP算法和二阶QP算法高,但比传统分支定界算法要低。仿真分析结果表明,在收发天线均为32的大规模MIMO场景下;在256QAM调制、误码率(bit error ratio,BER)为10-4时,比传统分支定界算法提升了约3 dB的性能增益,验证了算法对高阶调制的适应性。

摘要： 为了更好地解决二次约束二次规划问题(QCQP),本文基于分支定界算法框架提出了自适应线性松弛技术,在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分;通过缩减技术删除不包含全局最优解的部分区域,以加快算法的收敛速度。最后,通过数值结果表明提出的算法是有效可行的。

摘要： 投资者在进行投资组合选择时,通常希望得到的投资组合方案中,被选择资产数量可控,风险水平足够小。模型中通常以基数约束来控制投资组合方案中选择的资产数量。基于一类基数约束投资组合选择模型,该模型以最小化风险函数为目标,在不允许卖空前题下,考虑基数约束和预算约束。该模型应用极其广泛,但目前尚无商用软件可以直接精确求解。提出一种全局最优化算法,在分支定界法框架基础上,以一阶算法求解下界松弛问题。通过Fama-French产业投资组合基准测试数据集设计仿真实验,实验结果表明,本文提出的方法能有效解决带基数约束的产业投资组合问题,能够给出任意基数要求的全局最优投资组合方案。

摘要： 基于对某机场客舱清洁部门的实际调研,发现由于排班数据量过大,航班任务过多,难以与员工进行精确匹配,导致了目前该部门的排班人员仍在采取手工排班的方式对员工进行排班,大大加重了工作强度.基于以上问题,提出了一种更为高效的排班优化方案.该方法是在满足众多约束的条件下,根据现有的航班时刻表以及航班各项任务的服务指标,自动生成一份可用的精确的员工—任务相匹配的排班表,以实现员工工作时间均衡,航班任务有保障的优化目标.最终通过实验结果表明,该方法确切有效地解决了客舱清洁排班问题,并且具有较高的实际应用价值,极大地提高了排班效率和人力资源的利用率,破除了以往人工排班所夹杂的人为因素,形成了一套规范的排班约束准则,有效地改善了员工的工作时长,获得了较为公平公正的排班结果.

摘要： 目前,我国高速铁路列车一般采用固定编组形式,动车组运用效率较低,而未来可变编组列车投入使用后,运营组织方式将发生很大变化,需要优化列车开行计划以充分发挥可变编组列车的优势.研究可变编组列车在各技术区段的编组内容和组合拆解计划,以动车组开行成本最小和组合拆解作业时间最短为优化目标,构建可变编组列车开行计划优化模型,设计分支定界算法求解.以京沪高速铁路进行案例分析,结果表明:相比同等条件下固定编组模式,优化的可变编组列车开行计划可以提高列车客座利用率.

摘要： 无接触手势识别技术作为一种自然的人机交互方式,可以应用于手机、平板和可穿戴设备.为了高效实现超声手势识别嵌入式系统中采用的"一对其余"多分类随机森林算法,提出一种其推理过程的嵌入式软件实现方案.设计更精简的模型节点数据结构,以降低手势模型占用的存储空间.为节省系统能耗并缩短运行时间,利用分支定界的方法及时排除不可能产生正确解的手势类型,在保证识别率的条件下避免不必要的FLASH读取和决策树判定过程.实验结果表明,与传统的随机森林算法相比,该方案在FPGA上运行的实测时间缩短约60％,一次推理的平均判定次数低至243.

摘要： 本文为了获得二次约束二次规划(QCQP)问题的全局最优解,提出一种新的参数化线性松弛分支定界算法.该算法利用参数化线性松弛技术,得到(QCQP)的全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.数值实验表明,本文提出的算法是有效并且可行的.

摘要： 针对配电系统中存储的线变关系记录与实际运行情况不一致问题,基于能量守恒定理,从满足电量约束以及尽可能降低中压线路线损率波动幅度的角度出发,文章将配网线变关系智能识别问题转化为中压线路和配电变压器之间的组合优化问题,进而提出了一种配网线变关系识别模型.此外,为加快求解速度和提高识别准确率,通过合并电压波动相关性较高的配电变压器进行降维优化,之后采用分支定界算法进行求解.最后,基于用电信息采集系统获取的量测数据,利用MATLAB和CPLEX编程对所提方案进行实例分析,分析结果验证了识别方案的可行性和有效性.

摘要： 在线学习常常需要等质试卷来实施网络环境下的学习评价和测试,而目前的组卷系统大多在给定知识点覆盖和难度系数等的简单约束下从题库随机抽题,试卷质量得不到保证.本研究以项目反应理论(ItemResponse Theory,IRT)作为试卷质量的评估标准,先用分支定界优化算法从题库中产生若干道试题,再用最大团算法从备选试卷中生成差异化最大的一组等质试卷.用户可选的组卷参数包括题目类型,每种题型的题数和排列方式,考察知识点范围和每个知识点所占比例,试卷难度系数分布和区分度系数,试卷间的最大重叠题数和需要生成试卷的数量.系统生成的试卷严格满足题型约束,知识点覆盖约束和最大重叠题数约束,最小化知识点比例差异,根据IRT理论求出的信息函数差异,最大化出卷数量.

摘要： 为提高测试效率、降低测试代价,提出了一种基于故障字典与分支定界相结合的模拟电路测试点优化方法.以模糊集和故障字典为工具,以故障检测、故障隔离为约束,建立了测试点优化的0-1规划数学模型,并用分支定界法求解,最后用经典的测试优化电路对该方法进行仿真验证.仿真结果表明:上述方法在保证故障诊断需求的前提下实现了测试点快速优化,为实施测试提供了指导.

摘要： 给出了目标函数为最小化最大完成时间的k-阶段混合流水车间非排列排序调度问题的分支定界算法,介绍了此类问题特殊的复杂的分支树构建过程.根据分支树特点,提出了该类问题的一个新的下界.对9种问题规模共90组随机数据进行了算法性能测试,实验仿真结果表明,新提出的下界算法使原有算法提高了计算速度,改善了算法性能.

摘要： 近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询。首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念。其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法(Branch and Bound ρ-Dominant Skyline Algorithm,BBDS),避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率。最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证。实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法。

摘要： 目的：探索求解两个图最大公共子图的方法.方法：建立最大公共导出子图的软约束满足问题(Soft CSP)模型,提出代数决策图(ADD)的符号求解算法.首先,分别对两个图中的变量和值域进行编码,完成两个图的ADD表示;其次,基于深度优先分支定界算法的思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解.结果：算例结果表明,该方法准确可行.结论：该方法能有效缩减搜索空间,从而提高问题的求解效率.

摘要： 本发明提出了一种基于分支定界法的边缘计算任务分配方法，属于边缘计算领域。本发明在考虑任务完成时间以及DAG并行系统可靠性需求等约束的前提下最小化任务分配的总能耗。首先松弛上述优化问题，用内点法求得临时解；然后将临时解中第一个任务的决策变量取离散值并且满足一个任务只能在一个边缘服务器执行的约束,即决策变量只有一个取为1，其他均为0，将上述取值情况从第一个边缘服务器遍历到最后一个边缘服务器，对剩余任务继续采用内点法求解并计算不同解的能耗值，取能耗值最小的解，重复该步骤直至最后一个任务。本发明具有收敛性好、计算量小等优点。

摘要： 本发明公开了基于改进随机分支定界算法的复杂制造系统维修优化方法，包括以下步骤，步骤1，改进SB&B算法的初始化；步骤2，改进SB&B算法的分区；步骤3，采样可行解；步骤4，对采样解进行仿真；步骤5，对子区域进行边界估计；步骤6更新记录集。本发明的有益效果在于：在寻优算法(SB&B)中嵌入了一个序贯仿真过程，有效分配仿真资源，提高了仿真寻优算法的效率，为解决大规模的系统的仿真优化问题提供了参考。

摘要： 本发明公开基于分支定界内部诱导的机组组合方法，步骤包括：1)建立电力系统机组组合模型；2)构建系统阻塞灵敏度评估指标；3)建立小规模整数规划模型；4)利用分支定界方法确定机组组合方式。本发明通过分支定界内部诱导的方式，避免了因为修改模型而导致的最优性损失，进一步提高了UC的计算速度。

摘要： 本发明公开了一种基于分支定界法的多方式行车道精细化设置方法可以从城市多方式交通网络优化角度出发、考虑车道宽度在现有宽度约束下的最优组合，均衡私家车、公交车、非机动车等多种出行者出行权益的多方式道路空间分配，有效平衡城市多方式交通路权分配，提高城市道路空间利用效率，改善居民出行体验。

摘要： 本发明公开了一种求解旅游行程规划问题的新分支定界方法，步骤S1：在算法开始之前采集所有游客的信息；步骤S2：确定优化模型求解计算所需的参数；步骤S3：在考虑旅游资源资源限制的基础上，建立一个混合整数线性规划的优化模型来计算规划方案；步骤S4：针对该优化模型，利用新分支定界算法进行求解，最终得到游客总效用最大的旅游路线规划方案，该方案是全局最优解。本发明从对全域旅游的角度来考虑我国的旅游路线规划问题，可以改善传统旅游中可能出现的局部拥堵问题，有助于提高旅游服务系统效率和提高游客旅游满意度。

摘要： 本发明提出了一种基于分支定界的多视点三维点云数据的粗配准方法，包括：第一步：对待配准的三维点云数据特征点进行提取并得到点集；第二步：将第一步中得到的点集进行处理初步获取三维点云数据中的匹配点；第三步：将第二步中初步获得的匹配点集作为输入数据，进行特征点的进一步筛选，精确获取三维点云数据中匹配点；第四步：将第三步中得到的精确匹配点集作为输入数据，进行相机位姿参数估计，借此，本发明与现存的三维点云数据配准方法相比，本发明的方法使用的切比雪夫距离更加严格，具备速度快，准确率高的特点，能够更加快速、更加准确的进行粗配准，使得后续的精确配准过程更加节省计算资源和时间。

摘要： 本发明提出了一种基于分支定界的多视点三维点云数据的精配准方法，基于一种基于分支定界的多视点三维点云数据的粗配准方法实现，包括：第一步：旋转空间的参数化；第二步：平移空间的参数化；第三步：基于分支定界算法搜索最优参数，借此，本发明具有速度快、准确率高的特点，基于粗配准方式得出粗略估计结果后的精确配准结果，避免了直接使用Go－ICP算法得出错误结果或者陷入局部最优化等问题的优点。

摘要： 本发明提供一种基于分支定界算法的室内移动机器人定位方法，通过将深度相机和激光雷达采集的数据进行融合，采用分支定界的方法在离线地图中搜索全局初始位姿，再通过迭代最近点的方法对全局初始位姿进行优化，最后将该全局位姿作为激光雷达扫描匹配的全局初始位姿，之后通过相关性扫描匹配的方法不断计算机器人的当前位姿，该方式能够保证机器人在行进过程中的定位精度，减小机器人的累积误差。另外在激光雷达扫描匹配算法的运行过程中，采用分支定界的方法加速回环检测进行全局优化，当回环检测算法未能及时校正累积的误差时，采用重定位判断方法有效检测误差的累积状态，并通过调用全局定位算法校正累积误差，提高定位过程的准确性。

摘要： 本发明公开了一种基于分支定界的多期望信号下的阵列自适应波束形成方法，步骤如下：最大化输出信干噪比，同时采用线性分式半正定松弛方法降低阵列波束的副瓣电平；引入复数辅助变量，在保持期望信号的阵列响应的幅度不变的情况下，优化响应的相位，并用分支定界算法求解满阵的规划问题，实现多期望信号下的满阵自适应波束形成；引入迭代重加权l1范数对阵列的权向量进行惩罚，并用分支定界算法求解稀疏阵列的规划问题，实现多期望信号下的稀疏阵列自适应波束形成。本发明改善了多期望信号下的满阵和稀疏阵列的方向图性能，不仅降低了副瓣电平、提高了阵列的输出信干噪比，而且减小了多期望信号的方向图幅度误差。

摘要： 本发明公开了一种基于分支定界法的车辆安全任务卸载方法，应用在车辆自组织网络中。S1：获取车辆自组织网络的用户层的车辆用户集合，以及数据层中沿道路均匀分布的MEC服务器的集合，收集车辆用户安全消息任务；S2：根据车辆用户每个安全消息任务的最大时延容忍对安全消息任务进行排序，确定卸载的优先级顺序；S3：基于最优计算能力分配策略，以系统开销最小化为目标构建模型，利用分支定界法求解每个计算任务，确定任务卸载决策；S4：依据KKT条件，通过拉格朗日乘数法计算资源分配的最优解，通过该资源分配最优解完成车辆安全任务的卸载。本发明方法运用分支定界法解决得到最佳的卸载决策，可以降低安全消息的处理时延。