Integrated Research and Education in High-Performance Parallel Optimization Algorithms

高性能并行优化算法的综合研究和教育

• 批准号: 0102830
• 负责人: Nihar Mahapatra
• 金额: $ 20.08万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2006-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0102830&HistoricalAwards=false
• 关键词: Integrated; Research; Education; Performance; Parallel

Abstract for 0102830 Mahapatra"Integrated Research and Education in High-Performance Parallel Optimization Algorithms"This project will perform integrated research and education activities in the multidisciplinary area of parallel optimization. Given the enormous potential role of parallel computing in solving large-scale optimization problems with great societal implications, it is imperative that future scientists and engineers learn its fundamentals. The education component of this project will contribute towards bridging the current gap in knowledge of those professionals. The research activities center around efficient parallelization of an important optimization method called branch-and- bound (B&B), widely used for solving real-world combinatorial optimization problems (COPs). B&B's applications run the gamut of Science, Engineering, Mathematics, and Operations Research, with significant new uses being discovered every year. Research in B&B is performed by two groups of researchers: workers in parallel processing who use sophisticated parallelization techniques in conjunction with simple B&B algorithms, and hence are able to solve COPs of limited size; and workers in operations research who develop and use sophisticated application-specific B&B algorithms with little or no parallelism, to solve larger COPs. The overall objective of the proposed research is to improve solution time and quality for some important optimization problems by an order of magnitude, or to solve previously intractable problems, by applying scalable, high-performance parallelization techniques to application-specific B&B methods.Technically, the specific goals of the proposed project are as follows. (1) Adaptive Load Balancing: To develop load balancing schemes that adapt to application and target-system characteristics to maximize processor utilization. (2) Efficient Limited-Memory Search: To develop efficient search schemes that enable large problems to be solved within the available memory of practical parallel/distributed systems. (3) Specialized B&B Methods: To develop specialized B&B methods for some important COPs like mixed-integer programming and the traveling salesman problem, and use these to demonstrate solution time and quality improvements for real-world instances of those problems. (4) Parallel Optimization Course and Web Resource: To develop a model course on parallel optimization for upper-level undergraduate and beginning graduate students, as well as a comprehensive, searchable web resource on parallel optimization useful for education. (5) Parallel B&B Software Environment: To incorporate the parallelization techniques developed in this project in a software system for use as an educational and research tool for fast, efficient solution of optimization problems using parallel B&B.

摘要0102830 Mahapatra“高性能并行优化算法的综合研究和教育“该项目将在并行优化的多学科领域进行综合研究和教育活动。鉴于并行计算在解决具有重大社会影响的大规模优化问题中的巨大潜在作用，未来的科学家和工程师必须学习其基础知识。该项目的教育部分将有助于弥补这些专业人员目前在知识方面的差距。研究活动围绕一个重要的优化方法称为分支定界（B B），广泛用于解决现实世界的组合优化问题（COP）的有效并行化。B B的应用程序涵盖了科学、工程、数学和运筹学的各个领域，每年都有重要的新用途被发现。B B的研究由两组研究人员进行：并行处理的工作人员，他们使用复杂的并行化技术与简单的B B算法相结合，因此能够解决有限大小的COP;以及操作研究的工作人员，他们开发和使用复杂的特定于应用程序的B B算法，很少或没有并行性，以解决较大的COP。该研究的总体目标是通过将可扩展的高性能并行化技术应用于特定于应用的B B方法，将一些重要优化问题的求解时间和质量提高一个数量级，或者解决以前难以解决的问题。(1)自适应负载平衡：开发适合应用程序和目标系统特性的负载平衡方案，以最大限度地提高处理器利用率。(2)高效的有限内存搜索：开发高效的搜索方案，使大型问题能够在实际并行/分布式系统的可用内存内解决。(3)专门的B B方法：为一些重要的COP（如混合整数规划和旅行商问题）开发专门的B B方法，并使用这些方法来证明这些问题的实际解决方案的时间和质量改进。(4)并行优化课程和网络资源：为高水平的本科生和刚开始的研究生开发并行优化的示范课程，以及对教育有用的并行优化的全面的、可搜索的网络资源。(5)并行B& B软件环境：将本项目中开发的并行化技术纳入软件系统，作为使用并行B B快速有效解决优化问题的教育和研究工具&。