MIMD, SIMD, and Hybrid Parallelism for Network Optimization

并行算法的各种类别的大规模网络优化问题将开发和测试。研究将集中在以下几类网络流问题上：1 .纯单一商品2。广义（有增益和损失的网络）非线性 4所示。这些问题类跨越了非常广泛的大规模现实世界应用程序以及一系列数学类。它们也形成了一个自然的连续体，因为为前两类线性网络开发的并行技术通常与后两类相关，其中单一商品线性网络可能作为子问题出现。因此，这些领域之间存在协同关系。本研究的目标是统一和扩展并行优化的早期结果，以获得基于各种原始和对偶分解方法的有效算法，并适合在多计算机和多处理器架构上实现。这些方法将在本地可用的并行系统以及通过互联网可获得的其他并行硬件上进行大规模测试问题的测试。

Parallel algorithms for various classes of large-scale network optimization problems will be developed and tested. Research will focus on the following classes of network flow problems: l. Pure single-commodity 2. Generalized (networks with gains and losses) 3. Nonlinear 4. Multicommodity These problem classes span a very broad range of large-scale real-world applications as well as a spectrum of mathematical classes. They also form a natural continuum, since parallel techniques developed for the first two classes of linear networks are often relevant to the latter two classes, in which single-commodity linear networks may arise as subproblems. Thus, there are synergetic relationships between these areas. A goal of the research is to unify and extend earlier results in parallel optimization in order to obtain efficient algorithms that are based on a variety of primal and dual decomposition approaches and suited to implementations on multicomputer as well as multiprocessor architectures. These methods will be tested on large-scale test problems on the parallel systems available locally as well as on other parallel hardware available via Internet.