Adaptable and Scalable Techniques for Branching Algorithms

分支算法的适应性和可扩展技术

• 批准号: 9902092
• 负责人: Jonathan Eckstein
• 金额: $ 24万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9902092&HistoricalAwards=false
• 关键词: Adaptable; Scalable; Techniques; Branching; Algorithms

This project intends to advance the state of the art in applying parallel computing to branching algorithms. The term "branching algorithm" refers to any method built on the basic principle of branch-and-bound search for numerical optimization, including branch-and-bound, branch-and-cut, and branch-and-price methods.The software platform for the work will be PICO, a C++ class library package already being developed in cooperation with Sandia National Laboratories. The main goals for the continued development of PICO are:SCALABILITY: the software should scale efficiently up to hundreds or thousands of processors. While systems this large are rare today, and some of the "hype" surrounding them has quieted, a robust trend towards greater parallelism continues in the computer hardware industry. The project intends to develop technology that will continue to be useful as systems with more highly parallel CPU's become available.SYSTEMS PORTABILITY: the package should be adaptable, by changing its run-time parameter configuration, to varying communication/computation speed ratios. It should be usable on hardware from any vendor offering standard parallel software tools (C++ and MPI).APPLICATIONS PORTABILITY: the basic parallel search engine will be applicable to a wide variety of branching algorithms without duplication of the fundamental programming effort. The same core code should be able to manage parallel search applied to any branching algorithm, including relatively advanced methods like branch and cut. OBJECT ORIENTATION: extensible, object-oriented software design should help achieve the portability goals.

这个项目旨在推进在分支算法中应用并行计算的最新技术。分支算法是指任何基于分支定界搜索基本原理的数值优化方法，包括分支定界法、分支切割法和分支价格法。这项工作的软件平台将是皮科，一个已经与桑迪亚国家实验室合作开发的C++类库包。皮科持续开发的主要目标是：可扩展性：软件应有效扩展到数百或数千个处理器。虽然如此大的系统在今天已经很少见了，而且围绕它们的一些“炒作”已经平息，但在计算机硬件行业中，更大的并行性仍在继续。该项目打算开发的技术，将继续是有用的系统与更多的高度并行CPU的变得available.SYSTEMS便携性：该软件包应适应，通过改变其运行时的参数配置，以不同的通信/计算速度比。它应该是可用的硬件从任何供应商提供标准的并行软件工具（C++和MPI）。应用程序的便携性：基本的并行搜索引擎将适用于各种分支算法，而无需重复的基本编程工作。相同的核心代码应该能够管理应用于任何分支算法的并行搜索，包括相对高级的方法，如分支和切割。目标导向：可扩展的、面向对象的软件设计应该有助于实现可移植性目标。