解混合整数非线性规划问题并行分支定界算法研究
文献类型：学位论文
| 作者 | 胡四泉 |
| 学位类别 | 博士 |
| 答辩日期 | 2000 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 中国科学院软件研究所 |
| 关键词 | 并行处理 分支定界算法 混合整数非线性规划 |
| 学位专业 | 计算机软件与理论 |
| 中文摘要 | 混合整数非线性规划问题是最困难的最优化问题之一，它属于NP－安全问题；并行分支定界法是解NP－难的优化问题的著名方法，是保证在可接受的时间范围内得到最优解的重要途径。本文对解一般混合整数非线性规划问题的并行分支定界算法及其实现进行了综合研究，并对其在分布存储的MPP上的数值实验结果进行了分析。研究结果表明：（1）采用深度优先策略虽然能较快找到上界进行剪枝，但采用最优估计优先策略从整体性能上优于深度优先策略，因为它避免了在无希望的分枝上进行无谓的搜索导致的并行分支树的急剧扩张，从而的整体上节省了开销。（2）在MPI环境中，为了在各处理器间共享上界信息而进行广播是很自然的作法，但本文的实验结果表明，由于目前的MPI环境缺乏中断机制，为保护接收而进行的循环操作降低了效率，建议直接使用点对点通信。（3）在采用分布控制策略的AMP代码执行过程中，分支树较采用集中控制策略的ASP代码减小了约5％，但解题效率却下降了，概率方式的负载平衡未实现真正的任务均衡。（4）maximal fractional part分支规则与顺序分支规则比较，提高了解题效率，虽然幅度不大。（5）ASP算法执行时表现超线性加速和减速异常。出现减速异常的原因是分支树的数目随CPU的数量的增加而增大的趋势非常明显。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 43 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6892]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 胡四泉. 解混合整数非线性规划问题并行分支定界算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2000. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。