This is an award of supercomputer time. The object is to design and implement new algorithms which, by taking full advantage of parallel computing capabilities, will effectively solve large- scale, constrained, nonlinear global optimization problems on the shared-memory CRAY 2, CRAY X-MP, and CRAY Y-MP supercomputers. Constrained global optimization problems arise in many important areas of science and technology and include scheduling and allocation problems with nonconvex objective functions and a variety of computer-aided design and computational geometry applications. These kinds of optimization problems may possess many constrained local optima, but an acceptable solution to the problem requires that a global optimum, or a good approximation to it, be obtained. Because of the inherent difficulty of computing the global optimum, the emphasis of this research will be on the design and implementation of efficient algorithms which obtain an approximate solution to these problems on parallel computers in a reasonable amount of time. Typically these algorithms will find both an approximate solution and guaranteed bounds on this solution, with the accuracy of the approximate solution and the tightness of the bounds depending on the amount of computation performed. In view of this approach, primary interest is placed on the average, rather than worst case, behavior of these algorithms, and the performance analysis of this behavior will require a combination of both theoretical investigation and extensive computational testing.
