Core Technologies for Non-Linear Programming
Efficient nonlinear programming tools are essential for the optimization of large-scale engineering systems described by nonlinear models. Over the past 25 years we have developed three generations of NLP tools that have made major impacts in process optimization for model building, design and operations.
Starting in the 80s we developed, refined and applied Sequential Quadratic Programming (SQP) algorithms to deal with chemical processes including those described by comprehensive, detailed process simulators. In the 90s there codes were extended to deal with larger problems with many equations but relatively few degrees of freedom. Termed reduced space SQP (rSQP), these algorithms are widely used for applications in real-time optimization. The SQP and rSQP algorithms have formed the basis of commercial process optimization products by a number of vendors, including Aspen Technology and Simulation Sciences. In addition, we have worked with a number of operating companies in the CAPD consortium (e.g, Air Products, BP, Bayer, Eastman and ExxonMobil) on specialized applications that incorporate these codes. Moreover, an object oriented version of rSQP (called MOOCHO) has been extended and is currently part of the DAKOTA framework at Sandia National Labs.
Most recently, we have developed Newton-based barrier methods for large-scale optimization. This approach exploits second derivative information and deals with large numbers of constraints very efficiently. As a result problems with over a million variables and many thousands of degrees of freedom have been handled. This approach, called IPOPT, it currently maintained and developed further at IBM and
is widely applied in the optimization and engineering communities (including ABB, ExxonMobil, IBM, Invensys).
Associated Researchers: C. Laird, A. Raghunathan, A. Waechter, R. Bartlett,
D. Ternet, G. Staus, C. Schmid, S. Vasantharajan, J. Cuthrell
Optimization with Differential Equation Models
Building on the success of our nonlinear programming codes, we have been among the initial developers of collocation-based dynamic optimization. These methods have been adapted and refined for batch reactor optimization, nonlinear model predictive control and reactor network synthesis. Optimization applications include models with
several hundred differential algebraic equations. Among them are large, industrial-scale polymerization reactors, batch and continuous distillation columns, crystallization models, fuel cell systems and nonlinear process control. This approach has also been extended to models based on partial differential equations. These include periodic
adsorption processes, multiphase flow and complex reactors. Adaptations of these algorithms have also been incorporated in a number of industrial applications and commercial products (Aspentech, Invensys, Eastman Chemicals, ExxonMobil) for nonlinear model predictive control (NMPC) and real-time optimization (RTO).
Associated Researchers: V. de la Torre, C. Xu, A. U Raghunathan, T. Jockenhoevel, L. Jiang, N. Arora, G. C. Itle, L. Santos, A. Waechter, R. Bartlett, A. M. Cervantes,
T. Bhatia, A. Lakshmanan, P. Tanartkit, N. Oliveira, S. Balakrishna, J. Logsdon, W. Li, S. Vasantharajan, L. Achenie, J. Cuthrell
Parameter Estimation and Data Reconciliation
We have developed nonlinear programming formulations that are especially tailored to parameter estimation and system identification problems. In addition, nonlinear programming formulations have been developed with both Bayesian and robust forms of outlier detection and data reconciliation. These algorithms detect outliers while at the same time performing the data reconciliation or parameter estimation. This strategy has also been benchmarked and demonstrated by a number of researchers at other universities and has been applied on industrial projects (e.g., Amoco Chemicals, Mitsubishi Chemicals). Moreover, this approach has been applied to large-scale models arising from DAE and PDE applications. These include moving horizon estimation for process control, source detection for municipal water networks (with Sandia National Labs), parameter estimation for highly nonlinear polymerization processes (with ExxonMobil Chemicals) and media characterization for two-phase flow in reservoirs (ExxonMobil Upstream)
Associated researchers: I-B Tjoa J. Albuquerque, Y-D. Lang, G. Staus, N. Arora,
S. Kameswaran, C. Laird, M. Poku, V. Zavala
Mixed-Integer Nonlinear Programming
For more than 15 years we have been developing software for MINLP techniques. The most successful software implementation has been DICOPT which was incorporated in the commercial modeling system GAMS http://www.gams.com/solvers/solvers.htm#DICOPT. DICOPT is based on the outer-approximation method developed by Duran, Kocis and Viswanathan. DICOPT has been used by many companies of the CAPD. A recent implementation of MINLP techniques has been the open-source code for MINLP BonMin http://egon.cheme.cmu.edu/ibm/page.htm, which implements the branch and bound, outer-approximation algorithm and LP/NLP branch and cut method developed by Grossmann and co-workers. There is also the development of the new code LOGMIP for solving generalized disjunctive programming problems, which allows the handling of disjunctions and logic constraints http://www.logmip.ceride.gov.ar/. Companies that have made use of these techniques include Air Products, BP, Eastman Chemical, ExxonMobil
Researchers and associates:
Pierre Bonami, Aldo Vechietti, J. Viswanathan, Erwin Kavalangher (GAMS), Gary Kocis.
Most of the work in the area of process synthesis that has been applied in industry has been in the area of energy and separation systems http://newton.cheme.cmu.edu/interfaces/. Examples include MINLP models for the synthesis of heat exchanger networks and utility plants, heat integration modules for simultaneous optimization and heat integration, synthesis of integrated water treatment systems, synthesis of separation systems for olefin plants, and flowsheets for separation by crystallization and corn-based ethanol production. In addition we have developed models for the synthesis of distillation columns with rigorous models. Companies that have made use of these techniques include Air Products, Bayer, BP, Cargill, Eastman Chemical, Norsk Hydro, SimSci and UOP.
Researchers and associates:
Carlos Mendez, Sangbum Lee, Dmitry Golovashkin, Hector Yeomans, Truls Gundersen (Trondheim), Jeff Siirola (Eastman Chemical).
Process Planning and Scheduling
Mixed-integer planning and scheduling models of our group have seen rather extensive applications in industry, and produced significant savings. Examples include long range planning of networks of flexible processes, planning and scheduling of offshore gas and oilfields, multiperiod planning of utility plants, scheduling pf polymer plants, scheduling ethylene feedstocks, scheduling of plants for manufacturing dyes, planning and scheduling of plants with catalyst deactivation, scheduling for testing of new products, scheduling of roll mills, scheduling of consumer products, scheduling of pharmaceutical plants, scheduling of refinery operations. See: http://newton.cheme.cmu.edu/interfaces/ Companies that have made use of these techniques include ABB, Atofina, Dow Agrosciences, Dow Chemical, ExxonMobil, ICI, Kraverner, Mitsubishi, Unilever.
Researchers and associates:
Muge Erdirik, Carlos Mendez, Pedro Castro, Vikas Goel, Veronique, Bizet, Jennifer Jackson, John Wassick (Dow), Sarette Van den Heever, Vipul Jain, Gary Blau (Purdue), Ramesh Iyer, Craig Schmidt, Yakazu Natori (Mitsubishi), Leon Norton (Dow), Nikolaos Sahinidis, Turaj Thamassebee (Unilever), Bing Tjoa (Optience).
SPLIT - Synthesis of Nonideal Separation
Oliver Wahnschafft completed his Ph.D. thesis under the direction of Art Westerberg. The main thrust of his work was to create both insights and software for the synthesis of distillation column sequences to separate azeotropic mixtures. He called his research system 'SPLIT.' A major part of his work was to determine the limiting behavior of columns having two products and one feed (a simple column) and two products and two feeds (e.g., an extractive column). Oliver joined AspenTech and further developed the SPLIT system there, where it is now a widely used commercial product. He won a European award for innovative software product design for the
n-dim - Information Modeling for the Design
The n-dim group (including Eswaran Subrahmanian, Art Westerberg and many others) worked closely with the IT and product design departments of an industrial partner to develop the functional requirements for a web accessible document management system. The system passed through three prototypes to evolve the correct functionality. This company then purchased a commercial document system - to guarantee future software support -- and spent several
months tailoring it to have the functionality we demonstrated with the CMU system. They were extremely pleased with the collaboration. Use of this system rapidly spread throughout this company. We took the base system and further developed it into our LIRE' system, which we now use to support many class and research projects throughout Carnegie Mellon. The ICES community of researchers has also adopted LIRE' as its document management system.
Benchmarking and Documenting the Design Process
The n-dim group worked closely with a large product manufacturing company to develop a prototype system to "record" its design process for a particular "routine" but large product they specialized for each customer. Prior to the existence of this system, the company had no way to tie design successes and failures to the design process its engineers used. The design for the product is the setting of approximately 600 parameters, which engineers do iteratively by using 10 to 15 different tools. This system unobtrusively tracked the flow of data into and out of the product database, along with information on the tools the designers used to generate any new data. In the rapidly evolving sequence of prototypes, a graphical representation allowed designers and supervisors to replay any design path quickly. After a proof of concept using these prototypes, the company reimplemented a hardened commercial version for use in three of their
Global Optimization Algorithms and the BARON Software
A plethora of problems in science and engineering require the solution of nonlinear optimization problems with multiple local solutions. Our research in the area of optimization has recently led to the development of an all-purpose, rigorous global optimization methodology. Our main methodological results have included the development of a unifying framework for domain reduction; a theory of convex extensions that provides strong relaxations for a variety of mathematical programs; an entirely linear outer-approximation scheme for global optimization problems; finite branching schemes for certain continuous nonconvex problem classes; and the global optimization software package BARON. Scientists and engineers have used BARON in many application areas, including the development of new Runge-Kutta methods for partial differential equations, energy policy making, modeling and design of metabolic processes, product and process design, engineering design, and automatic control. Since commercial versions of BARON were made available under the GAMS and AIMMS modeling systems, BARON has been used by several companies in the automotive, financial, and chemical process industries.
Associated Researchers: H. S. Ryoo, V. Ghildyal, M. C. Dorneich, R. A. Gutierrez, M. L. Liu, J. P. Shectman, N. Adhya, S. Ahmed, M. Tawarmalani, A. Vaia, Y. Chang, X. Bao.
Crystallographic Computing and Molecular Imaging
Since the mid nineteen hundreds, analysis of X-ray diffraction data of crystals has been used extensively for the determination of molecular structure and properties. While the method is employed almost on a routine basis worldwide, it is often a major challenge to identify the 3D structure that best fits the diffraction data. A key obstacle, known as the “phase problem” in crystallography, involves the identification of the phases of the diffracted rays from measurements of intensities alone. The lack of universally applicable algorithms for this problem often requires experimentalists to synthesize and crystallize variants of the compound under study, a requirement that we would like to entirely eliminate. We have developed an optimization methodology for solving a constrained minimal principle formulation of the phase problem. This methodology leads to considerably more accurate structures in comparison to state-of-the-art crystallographic software. Recently, our algorithms have been incorporated into the widely distributed crystallographic computing system Shake-and-Bake developed by the group of Chemistry Nobel Laureate Hauptman at the Hauptman-Woodward Medical Research Institute. As a result, our algorithms are now available to a large user base of industrial and academic crystallographers worldwide.
Associated Researchers: A. Vaia, A. B. Smith.
Bioinformatics Algorithms and Software
As modern biology is becoming increasingly data-driven, it has become apparent that many protein bioinformatics problems can be solved through optimization of a merit function that evaluates alternatives from very large, often combinatorial, search spaces. We have developed novel optimization models and algorithms for a variety of challenging bioinformatics problems. These problems include prediction of protein side-chain structures from knowledge of backbone structures, three-dimensional (structural) alignment of proteins, DNA sequencing by hybridization, design of combinatorial libraries, design and reconstruction of metabolic and signaling networks from time-series data, and protein binding site identification. Our algorithms for these problems are currently the fastest available exact algorithms for these problems in the bioinformatics literature. Software implementations for the first three of these problems are available to the research community via our bioinformatics software web page. Our R3 on-line solver for the protein side-chain problem has been used by other researchers in the CASP protein structure prediction competition, while our CMOS on-line server for the protein structural alignment has been used by several researcher groups to evaluate the quality of newly proposed heuristics for protein alignment.
Associated Researchers: W. Xie, Y. Chang.