Integrated Research and Education in High-Performance Parallel Optimization Algorithms

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

• 批准号: 0627835
• 负责人: Nihar Mahapatra
• 金额: $ 1.22万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-10-08 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0627835&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）的重要优化方法的有效并行化，该方法广泛用于解决现实世界中的组合优化问题（COPS）。 B＆B的应用程序运用了科学，工程，数学和运营研究的范围，每年都会发现重要的新用途。 B＆B的研究由两组研究人员进行：与简单的B＆B算法结合使用复杂的并行化技术的平行处理工人，因此能够解决规模有限的COP；以及开发和使用几乎没有或没有并行的特定应用程序特定的B＆B算法的运营研究工人来解决较大的警察。拟议的研究的总体目标是通过将可扩展的高性能并行技术应用于应用特定的B＆B方法来提高某些重要优化问题的解决方案时间和质量，或者通过将可扩展的高性能并行技术应用于拟议项目的特定目标，如下所示项目。 （1）自适应负载平衡：开发适应应用程序和目标系统特征以最大化处理器利用率的负载平衡方案。 （2）有限的有限内存搜索：制定有效的搜索方案，使大型问题能够在可用的实用并行/分布式系统的可用内存中解决。 （3）专业的B＆B方法：为一些重要的警察开发专业的B＆B方法，例如混合企业编程和旅行推销员问题，并使用这些方法来证明解决方案的时间和质量改进，以实现这些问题的现实情况。 （4）并行优化课程和Web资源：为高级本科生和初学者的平行优化开发模型课程，以及有关对教育有用的并行优化的全面，可搜索的Web资源。 （5）并行B＆B软件环境：将本项目中开发的并行化技术合并到软件系统中，用作使用并行B＆B快速，有效解决优化问题的教育和研究工具。