Adaptable and Scalable Techniques for Branching Algorithms

该项目旨在推动将并行计算应用于分支算法的最新技术。分支算法是指建立在数值优化的分支定界搜索基本原理上的任何方法，包括分支定界法、分支切割法和分支价格法。这项工作的软件平台将是Pico，这是一个已经与Sandia国家实验室合作开发的C类库程序包。Pico继续开发的主要目标是：可伸缩性：该软件应该高效地扩展到数百或数千个处理器。尽管如今如此大的系统很少见，一些围绕它们的“炒作”也已经平息下来，但计算机硬件行业仍在继续朝着更大程度的并行性发展。该项目旨在开发将继续有用的技术，随着具有更高并行CPU的系统变得可用。SYSTEMS可移植性：通过改变其运行时参数配置，该包应该能够适应不同的通信/计算速度比。它应该可以在任何提供标准并行软件工具(C和MPI)的供应商的硬件上使用。可移植性：基本的并行搜索引擎将适用于各种分支算法，而不需要重复基本的编程工作。相同的核心代码应该能够管理应用于任何分支算法的并行搜索，包括相对先进的方法，如分支和切割。面向对象：可扩展的、面向对象的软件设计应该有助于实现可移植性目标。

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.