(4p) Advanced Strategies for Large-Scale Optimization Problems: Applications in Homeland Security

Effective solution of problems in Process Systems Engineering requires careful consideration of the application domain and the solution techniques, from both a theoretical standpoint and a computational standpoint. In this work we have focused on careful formulation of large scale optimization problems and the development of IPOPT 3.0.0, a general framework for efficient solution of structured large-scale nonlinear programs (NLPs). In this poster, I will outline our existing work developing nonlinear programming approaches for inverse problems in large networks and indicate future plans to handle uncertainty in these large problems. I will also discuss research ideas for optimization of disease spread models, allowing online optimal control in the face of an impending epidemic. To enable efficient solution of these and other large-scale problems, I will also outline plans for the development of efficient numerical approaches for the solution of structured nonlinear programs.

In collaboration with colleagues at Sandia National Laboratories in Albuquerque, New Mexico, we have examined contamination source inversion in drinking water networks that span large urban centers. Given a contamination in a large city, we use time-dependent concentration measurements from a limited sensor grid, coupled with network flow information, to invert for the time and location of the contamination source. Making no assumption about the location of the contamination, we introduce unknown, time-dependent injections at every node in the network (thousands). We then formulate a least squares estimation problem, subject to the constraints of the dynamic water quality model (PDE and DAE), to solve for the injection profiles.

This problem is difficult because of a number of characteristics: 1) There are a large number of degrees of freedom resulting from the complete time discretization of the unknown injections at every node. Sequential techniques which rely on finite difference derivatives or sensitivity equations are, therefore, inefficient and we consider a simultaneous approach. Discretizing the entire system in both time and space produces a nonlinear program that is far too large for current tools, however, using our origin tracking algorithm, remove the need to discretize in space, reducing the problem size dramatically. This allows efficient real-time solutions for these large network problems. 2) Each degree of freedom is bounded to be non-negative. With such a large number of variable bounds, we use an interior point NLP code, IPOPT (www.coin-or.org), to avoid the combinatorial expense of an active-set strategy. 3) Drinking water networks are themselves very large and consideration of the entire network may not be possible. We show how a moving window approach can be used to reduce the problem size and allow efficient inversion solutions. 4) The estimation problem has non-unique solutions that arise because of the network topology, flow patterns, and the sparse sensor grid. This produces directions of zero curvature in the projected hessian and, because of this, we regularize the problem to force a single unique solution. This regularized solution is an approximate linear combination of the family of possible injection scenarios. Furthermore, multiple contamination events may be occurring in the network. We formulate a mixed integer quadratic program (MIQP) to search the regularized solution space and are able to distinguish the number of injections and the distinct injection scenarios that give rise to the observed concentrations. Future work concerning contamination of large networks includes handling uncertain network flows and the daunting control problem. I will outline future plans to tackle these issues.

With recent events surrounding SARS and avian flu, there is increased concern over an epidemic outbreak. This has sparked increased research efforts into dynamic modeling of disease spread in individual communities and over larger areas. Since each situation is unique, general policies for handling an epidemic outbreak are insufficient and, with the development of accurate disease spread models, the time is opportune for tackling the inverse problems of source identification and control. I will briefly outline a research agenda that develops online optimization techniques for source identification and control of these systems.

The success of large scale optimization often relies on the ability to exploit any structure that exists in the problem. Interior point methods are particularily well suited to handling specialized problems since the structure of the KKT system is the same for each iteration. As a co-author of the recently released IPOPT 3.0.0, the primary design goal was to create an object-oriented, nonlinear programming tool that would easily allow specialized linear algrebra for the solution of large-scale, structured problems. Here, I demonstrate the use of this capability to implement an efficient solution approach for problems with block-bordered KKT systems. Block-bordered KKT systems result from a number of applications including design under uncertainty, spatial decomposition, and multi-stage dynamic optimization. We will demonstrate this structured solution technique with an optimization under uncertainty problem.

Chemical engineering principles of modeling, optimization, and control of complex systems, show significant promise for the two non-traditional research areas described above. Success in both the areas will require efficient solution of large-scale structured nonlinear programs and my research plan is to develop approaches for efficient solution of previously intractable, large-scale problems. The numerical approaches developed for these problems can also be used to solve more traditional chemical engineering problems. Certainly, careful consideration of the application domain, the problem formulation, and the development of advanced numerical approaches will allow us to consider applications not previously solvable with standard techniques.