Large-Scale Optimization Via Distributed Systems.

摘要

Most large-scale network optimization problems exhibit structures that allow the possibility of attack via algorithms that exhibit a high degree of parallelism. Such structures include quasi-independent blocks of constraints for different commodities or time periods, and geographically disjoint components in approximating solutions. The emphases of our research have been the development of new parallel optimization techniques that utilize these and related features in order to take advantage of distributed computing environments. We have also undertaken a comparison of the relative efficiencies of approaches based on different computer architectures such as message-passing multicomputers and shared-memory multiprocessors. The parallel algorithms that we have implemented have made possible the solution of extremely large linear networks (with more than 1 million variables) and nonlinear network optimization problems with as many as 400,000 variables or relatively modest parallel computing systems, and have displayed excellent speedups relative to the corresponding single-processor programs. (kr)