A symbolic reformulation/spatial branch-and-bound algorithm for the globaloptimization of nonconvex MINLP's

Many important tasks in process design and operation can be formulated math ematically as NLP and MINLP optimization problems. These are often nonconve x. and the application of standard local optimization techniques to them of fers no guarantee that any solution(s) generated will correspond to the des ired 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 operatio n problems are to realize their full value, determining globally optimal so lutions is of paramount importance. This paper is concerned with the global optimization of MINLP problems defi ned in the context of general-purpose process modeling software in which th e same model is used for a variety of applications such as simulation, opti mization. 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 o bjective function that will be posed by the users. Secondly, it would be un reasonable to require the users to present different formulations of the sa me problem depending on the application that they are currently considering ; in fact, most users will probably not have the mathematical background th at would allow them to determine the best way of formulating their problem for any particular type of application. We are, therefore, interested in al gorithms that have wide applicability while requiring very little, if any, user intervention beyond the definition of the problem in a high-level mode ling language. A two-step symbolic/numerical approach to achieving the above objectives is proposed. First, a symbolic reformulation technique is applied to the prob lem posed by the user in order to transform it automatically to a standard form that is amenable to solution by sBB global optimization algorithms. Th e reformulation procedure is applicable to any set of objective function an d constraints, the symbolic form of which is available explicitly. As a second step, a general sBB algorithm is applied to the standard form r esulting from the symbolic reformulation. The algorithm is, in principle, a pplicable 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 t he relative order of branching on the discrete and continuous variables in the MINLP. Instead, the algorithm attempts to choose the most promising var iable on which to branch at each node of the search tree. The combined symbolic/numerical algorithm has been implemented within the g PROMS process modeling tool. Particular emphasis has been placed on the eff icient utilization of memory during the sBB search and on the parallelizati on of this algorithm for execution on computers with a distributed architec ture. The applicability of the algorithm has been illustrated via its appli cation to the solution of a set of nontrivial process engineering problems.