- Previous Article
- Next Article
- Table of Contents
Computers & Chemical Engineering, Vol.25, No.11-12, 1399-1401, 2001
A symbolic reformulation/spatial branch-and-bound algorithm for the global optimization of nonconvex MINLP's
Many important tasks in process design and operation can be formulated mathematically as NLP and MINLP optimization problems. These are often nonconvex. and the application of standard local optimization techniques to them offers no guarantee that any solution(s) generated will correspond to the desired global optimum. The latter is often quite different (e.g. with respect to process flowsheet structure) than local solutions to the same problem. Consequently, if mathematical programming approaches to design and operation problems are to realize their full value, determining globally optimal solutions is of paramount importance. This paper is concerned with the global optimization of MINLP problems defined in the context of general-purpose process modeling software in which the same model is used for a variety of applications such as simulation, optimization. and parameter estimation. This has certain important implications regarding the properties of the algorithms that we can develop. First, we can make few assumptions regarding the form of the constraints and/or the objective function that will be posed by the users. Secondly, it would be unreasonable to require the users to present different formulations of the same problem depending on the application that they are currently considering; in fact, most users will probably not have the mathematical background that would allow them to determine the best way of formulating their problem for any particular type of application. We are, therefore, interested in algorithms that have wide applicability while requiring very little, if any, user intervention beyond the definition of the problem in a high-level modeling language. A two-step symbolic/numerical approach to achieving the above objectives is proposed. First, a symbolic reformulation technique is applied to the problem posed by the user in order to transform it automatically to a standard form that is amenable to solution by sBB global optimization algorithms. The reformulation procedure is applicable to any set of objective function and constraints, the symbolic form of which is available explicitly. As a second step, a general sBB algorithm is applied to the standard form resulting from the symbolic reformulation. The algorithm is, in principle, applicable to any MINLP, the objective function and constraints of which are constructed from the basic operations of arithmetic and any purely convex or purely concave univariate function. No a priori decision is made as to the relative order of branching on the discrete and continuous variables in the MINLP. Instead, the algorithm attempts to choose the most promising variable on which to branch at each node of the search tree. The combined symbolic/numerical algorithm has been implemented within the gPROMS process modeling tool. Particular emphasis has been placed on the efficient utilization of memory during the sBB search and on the parallelization of this algorithm for execution on computers with a distributed architecture. The applicability of the algorithm has been illustrated via its application to the solution of a set of nontrivial process engineering problems.