| 解混合整数非线性规划问题并行分支定界算法研究 |
| 胡四泉
|
| 专业 | 计算机软件与理论
|
| 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. |
| 页数 | 43
|
| 语种 | 中文
|
| 内容类型 | 学位论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/6892
|
| 专题 | 中科院软件所_中科院软件所
|
推荐引用方式
GB/T 7714 |
胡四泉. 解混合整数非线性规划问题并行分支定界算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所,2000.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论