Modelling for Parallel Optimization

As a result of the development of both research and commercial multiprocessors and multi-computers capable of implementing parallel algorithms for optimization, there has been a renewed interest in both theoretical and computational aspects of such techniques. From a modelling viewpoint, it becomes important to formulate the problem in such a manner that it can be decomposed into quasi-independent subproblems that are suited to the computer architecture on which it will be solved. One key issue in this regard is the granularity of the computation, i.e. the sizes of the ‘pieces’ that will be dealt with in parallel. For example, in a traffic assignment problem, one has the option of defining commodities (and hence subproblems) by origin-destination pair og by origin. The latter approach is less traditional, but gives rise to larger sub-problems that are better suited to a computing environment in which communication between processors is relatively expensive. Thus, one method of dealing with granularity is to seek to modify an existing model in such a way as to facilitate the decomposition of the problem into subproblems of appropriate size. A related issue is whether one will initialize the decomposition process by using intrinsic structures available a priori from the model (such as commodities or time periods) or exploit the previous solution of a related problem (which may, for example, allow a tentative geographic decomposition of the area covered by the model), or employ a heuristic splitting procedure based on the current problem data and then dynamically modify the structure of the decomposition as needed during the course of the solution process. It is clear that in order to reduce the amount of information exchange and to accelerate the solution process, it is desirable to partition the model in a manner that is suited to the machine architecture and reflects as much as possible a partition related to an optimal solution. These topics will be addressed in the context of research on large-scale nonlinear and generalized networks. We will describe computational experience with two parallel computing systems at the Computer Sciences Department of the University of Wisconsin: the CRYSTAL multicomputer, a loosely-coupled token-ring network of 20 VAX 11/750’s, and the Sequent Balance 21000, a commercial shared-memory multiprocessor with 8 processors.