Integrated Research and Education in High-Performance Parallel Optimization Algorithms

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

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.