Scalable Parallel Algorithms for Large-Scale Discrete Optimization

点击翻译按钮获取中文摘要

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.