Scalable Parallel Algorithms for Large-Scale Discrete Optimization

用于大规模离散优化的可扩展并行算法

• 批准号: 0102687
• 负责人: Theodore Ralphs
• 金额: $ 20.04万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0102687&HistoricalAwards=false
• 关键词: Scalable; Parallel; Algorithms; Large; Scale

This project will develop scalable algorithms for solving discrete optimization problems (DOPs) in distributed-memory computing environments. DOPs arise in many important applications such as planning, scheduling, logistics, telecommunications, bioengineering, and robotics. Most of these problems are NP-complete, but in practice, intelligent search algorithms such as Branch, Cut, and Price (BCP) have been successful at tackling them. This research will develop parallel algorithms based on BCP that not only can use large numbers of processors efficiently, but also can handle very large problem instances. A key part of these algorithms is the data structure used for maintaining the information for each node in the search tree. This can be implemented with a memory-efficient differencing scheme relating the parent and child nodes. However, these data structures do not allow the use of current techniques for implementing scalable branch and bound search algorithms. This project will overcome that difficulty.The project will build on previous work in which the PI developed an object-oriented, generic framework called SYMPHONY (Single- or Multi-Process Optimization over Networks). Because of its modular design, SYMPHONY is extremely flexible and can be used to solve a wide variety of DOPs. Source code and documentation for SYMPHONY is currently distributed for free to the research community. This project will develop data structures and load balancing methods to decentralize SYMPHONY's current centralized control and data storage model. These improvements will be added to the web-based distribution to improve the impact of this project.

这个项目将开发可扩展的算法，用于解决分布式内存计算环境中的离散优化问题（DOP）。DOP出现在许多重要的应用中，如规划，调度，物流，电信，生物工程和机器人。这些问题中的大多数是NP完全的，但在实践中，智能搜索算法，如分支，切割和价格（BCP）已经成功地解决了这些问题。本研究将发展以BCP为基础的平行演算法，不仅可以有效地使用大量的处理器，而且可以处理非常大的问题实例。这些算法的关键部分是用于维护搜索树中每个节点的信息的数据结构。这可以通过将父节点和子节点相关的内存高效差分方案来实现。然而，这些数据结构不允许使用用于实现可缩放的分支和边界搜索算法的当前技术。这个项目将克服这个困难。这个项目将建立在PI以前的工作中，其中PI开发了一个面向对象的通用框架，称为SYMPHONY（网络上的单或多进程优化）。由于其模块化设计，SYMPHONY非常灵活，可用于解决各种DOP。SYMPHONY的源代码和文档目前免费分发给研究社区。该项目将开发数据结构和负载平衡方法，以分散SYMPHONY当前的集中控制和数据存储模型。这些改进将添加到基于网络的分发中，以提高该项目的影响。