


Parallel Optimization and Automatic DifferentiationJohn Dennis (director), Christian Bischof, Robert Bixby, Alan Carle, George Corliss, John Elder, Robert Michael Lewis, Jorge More, Danny Sorensen, Richard Tapia, Virginia Torczon, Steve Wright, and Xiaodong ZhangOptimization calculations are a staple of numerical computation. They are used by industry in planning, design, marketing, and distribution. Rarely does modeling not involve at least one optimization stage; and since the point of modeling is either control or improvement of the process being modeled, a second optimization stage is often required. The CRPC Parallel Optimization group is developing parallel algorithms motivated by applications for optimization calculations on parallel machines. The overall goal of the Parallel Optimization project is to learn to use parallel computer systems to solve optimization problems of interest to industry and academia in which lack of computing speed or power are the major bottlenecks. Major emphasis is on linear and integer programming and on multidisciplinary design optimization. One project is the development of an environment for large scale optimization problems that only requires the user to provide code to evaluate a partially separable function. This novel approach eliminates the need to provide the gradient and sparsity pattern; in all other approaches the user is required to provide the gradient and (for a Newton method) the sparsity pattern. This will provide a unique capability that it not available elsewhere. John Dennis' research is on practical methods for optimization with particular interest in parallel methods for nonlinear optimization of systems described by coupled nonlinear simulations. He is editorinchief and founder of the SIAM Journal for Optimization, an advisory editor of Mathematics of Operations Research, and a past coeditor of Mathematical Programming. He has served as chair of the SIAM Activity Group for Optimization, and he served two terms on the SIAM Council. He has done extensive consulting for United States industry, has been a Fullbright Lecturer to Argentina, and has published his algorithm research in several widely disseminated software journals. Dennis has given many short courses and featured addresses at international conferences. He has directed 27 Ph.D. theses, and his students hold positions in industry, government, and academic departments of business, mathematics, computer science, and applied mathematics. His textbook, coauthored with R.B. Schnabel, was published by PrenticeHall and in Russian translation by Mir. Linear ProgrammingBoth business and engineering rely heavily on linear programming to find the best solutions under linear constraint criteria. The research group's major emphasis in linear programming over the next five years will be in the development of parallel interiorpoint methods. Researchers will test ideas for parallelizing interiorpoint approaches to linear programming through the use of Arnoldi methods developed from the CRPC Linear Algebra project. Work on simplex approaches will concentrate on parallel procedures that exploit special structure, such as block angular adaptive procedures. In addition, airline crew scheduling problems will be tested on an Intel Delta using a parallel steepestedge simplex algorithm for problems with a large column/row ratio and column homogeneity. One problem that uses this algorithm will have 13,000,000 variables.Christian Bischof devised the concept of incremental condition estimation, which enabled novel approaches to the computation of rankrevealing factorizations. He also was one of the developers of the publicdomain LAPACK linear algebra library. As part of his CRPCsupported work, he is one of the initiators of the ADIFOR project for a portable Fortran automatic differentiation system. Bischof was the first recipient of the Wilkinson Fellowship in Computational Mathematics, awarded by Argonne National Laboratory in 1988. He is the author of more than 50 articles and technical reports. Multidisciplinary OptimizationA fundamental challenge for computational engineering is MDO or multidisciplinary optimization. MDO is the identification, control, design or analysis of systems and products described by coupled simulations. It is difficult to overemphasize the economic importance of developing this capability that will facilitate rapid prototyping of new designs and decrease product timetomarket. Meeting this challenge is crucial to any realization of agile manufacturing, and to greater customer satisfaction through optimization of lifecycle costs, including maintenance and recycliblity.The CRPC effort in MDO involves collaborative research with Boeing and with MADIC, a consortium of major aerospace and automobile manufacturers. The major result to date has been a modeling framework for MDO that has led to a reformulation suitable for a parallel solution on a heterogeneous network of parallel supercomputers and workstations. Automatic DifferentiationFor accurate sensitivity information on solvers, researchers in the Parallel Optimization group are utilizing ADIFOR (Automatic Differentiation in Fortran), the CRPCdeveloped automatic differentiation tool that is a crucial technology for largescale optimization problems. ADIFOR has convincingly demonstrated that large Fortran codes can be automatically processed to provide the user with valuable derivative information. As a result, iterative processes can be accelerated, model parameters optimized, and the sensitivity of results with respect to initial conditions and control actions quantified.These beneficial effects have been obtained on trajectory optimization programs (Boeing), optimal design of membrane filtration processes (Rice University), threedimensional NavierStokes codes for transonic flow (NASA), car engine lubrication simulations (General Motors), and biomechanical models of complex human organs (National Institute of Standards and Technology). Robert Bixby is interested in linear, integer, and combinatorial optimization problems, with a particular emphasis on the solution of largescale, realworld models. Current projects include the study of cuttingplane techniques (both sequential and parallel) for the Traveling Salesman problem, parallel mixed integer programming, and methods for combining simplex and interiorpoint methods in the solution of largescale linear programs. He is EditorinChief of Mathematical Programming. Nonlinear ProgrammingAn important use of nonlinear optimization is to determine parameters in systems described by differential equations. Nonlinear programming has widespread applications in environmental and energy research as well as in engineering design, where it is the core of modern concurrent engineering.In system modeling applications, the system's future behavior may be predicted by using past observational data of the system's states to determine its characterizing parameters. This first optimization stage is called the inverse problem solution or parameter identification stage. Once this is done, emphasis shifts to the determination of the design or control parameters that optimize some system performance index. The group has applied new codes being developed to determine 4,100 spline coefficients for hydraulic conductivity from pressure data. This effort involved using the Intel Delta to solve a 96,000variable nonlinear programming problem with 92,000 nonlinear constraints. Integer ProgrammingInteger programming work focuses on using the structure of particular classes of hard combinatorial problems to define specific types of exact cuttingplane methods that require little or no branching. Given this sequential procedure and the availability of a powerful parallel machine, researchers will "weaken" or step back from the full sequential cuttingplane procedure enough so that the problem is fragmented and the available processors can be used. This approach combines the advantages of a mathematically powerful algorithm with the capability of machines that will have thousands of processors.Cuttingplane methods embedded in branchandbound techniques have been applied with particular success to the Traveling Salesman Problem (TSP). Examples have shown TSP instances that can be solved on five to seven processors of an Intel iPSC/860 hypercube at speeds equaling that of a singleprocessor CRAY YMP. The group is testing this approach on the Intel Delta, as well. Working with researchers at the Center for Discrete Mathematics and Theoretical Computer Science, another NSF Science and Technology Center, CRPC researchers are restructuring the parallel TSP code in order to incorporate the lessons learned in solving a worldrecord 3038city problem on a network of heterogeneous workstations. These same collaborators are also building a mixed integerlinear programming code exploiting the work on TSP and other major advances in pure integer programming during the past ten years. Jorge More is interested in the development of algorithms and software for optimization problems and their performance on vector and distributedmemory architectures. He played the lead role in the development of MINPACK1, a collection of highquality optimization subroutines distributed worldwide to more than 500 sites. He is currently working on an expanded version of the MINPACK package, with a focus on largescale optimization. More is on the editorial boards of Numerische Mathematik and the SIAM Journal on Optimization, and has been on the editorial boards of the SIAM Journal on Numerical Analysis and the SIAM Journal on Scientific and Statistical Computing. He recently finished a book with Stephen Wright, Optimization Software Guide, published by SIAM. Sites & Affiliations  Leadership  Research & Applications  Major Accomplishments  FAQ  Search  Knowledge & Technology Transfer  Calendar of Events  Education & Outreach  Media Resources  Technical Reports & Publications  Parallel Computing Research Quarterly Newsletter  News Archives  Contact Information
