Scalable Parallel Algorithms for Large-Scale Discrete Optimization

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

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.