中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
解混合整数非线性规划问题并行分支定界算法研究
作者: 胡四泉
答辩日期: 2000
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 并行处理 ; 分支定界算法 ; 混合整数非线性规划
摘要: 混合整数非线性规划问题是最困难的最优化问题之一,它属于NP-安全问题;并行分支定界法是解NP-难的优化问题的著名方法,是保证在可接受的时间范围内得到最优解的重要途径。本文对解一般混合整数非线性规划问题的并行分支定界算法及其实现进行了综合研究,并对其在分布存储的MPP上的数值实验结果进行了分析。研究结果表明:(1)采用深度优先策略虽然能较快找到上界进行剪枝,但采用最优估计优先策略从整体性能上优于深度优先策略,因为它避免了在无希望的分枝上进行无谓的搜索导致的并行分支树的急剧扩张,从而的整体上节省了开销。(2)在MPI环境中,为了在各处理器间共享上界信息而进行广播是很自然的作法,但本文的实验结果表明,由于目前的MPI环境缺乏中断机制,为保护接收而进行的循环操作降低了效率,建议直接使用点对点通信。(3)在采用分布控制策略的AMP代码执行过程中,分支树较采用集中控制策略的ASP代码减小了约5%,但解题效率却下降了,概率方式的负载平衡未实现真正的任务均衡。(4)maximal fractional part分支规则与顺序分支规则比较,提高了解题效率,虽然幅度不大。(5)ASP算法执行时表现超线性加速和减速异常。出现减速异常的原因是分支树的数目随CPU的数量的增加而增大的趋势非常明显。
英文摘要: Mixed integer nonlinear programming problems are one of the most difficult optimization problem and it is NP-Complete; parallel branch-bound algorithm is a well-known method for solving NP-difficult problems and it is a important way to get the optimal in acceptable time range. The thesis synthesizes the parallel branch-and-bound algorithm and it's implementation, describes our numerical experiments on several test problems within a distributed-memory massively parallel processing machine. Our main conclusions are as following: ◆ Parallel branch-and-bound algorithm employing the depth-first strategy could get an upper bound to prune faster than best-first strategy, but the latter achieves better effect on the whole for avoiding exhausted search on the unpromising branch. ◆ To sharing the upper bound in MPI environment, it is natural to broadcast. However our experiment results show that without interrupt facility MPI's loop operations to receive messages get poor efficiency, which favors the reversal, point-to-point communication. ◆ In our implementations, the BB tree of AMP code using distributed-control strategy is 5% smaller than that of ASP code using central-control strategy, while the latter is more efficient, which shows the probabilistic dynamic-balance method doesn't achieve the real run-time task equilibrium. ◆ The "maximal fractional part" branch rule performs better than the sequential branch rule, although which is trivial in out implementation. ◆ In our implementations, ASP algorithm achieves super-linear speedups and deceleration anomalies. The cause of the latter is the evident trend of expanding the BB tree with increasing the CPU numbers.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6892
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW002132.pdf(1160KB)----限制开放-- 联系获取全文

Recommended Citation:
胡四泉. 解混合整数非线性规划问题并行分支定界算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2000-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[胡四泉]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[胡四泉]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace