Adaptable and Scalable Techniques for Branching Algorithms

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

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.